perm filename KNOWL[AM,DBL]2 blob
sn#386215 filedate 1978-10-07 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00026 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 .NSECP(AM's Concepts)
C00006 00003 .SSEC(Motivation and Overview)
C00009 00004 . SSSEC(A Glimpse of a Typical Concept)
C00017 00005 . SSSEC(The main constraint: Fixed set of facets)
C00027 00006 . SSSEC(BEINGs Representation of Knowledge)
C00031 00007 .SSEC(Facets)
C00037 00008 . SSSEC(Generalizations/Specializations)
C00048 00009 . SSSEC(Examples/Isa's)
C00062 00010 . SSSEC(In-Domain-of/In-Range-of)
C00076 00011 . SSSEC(Views)
C00086 00012 . SSSEC(Intuitions)
C00095 00013 . SSSEC(Analogies)
C00105 00014 . SSSEC(Conjec's)
C00125 00015 . SSSEC(Definitions)
C00141 00016 . SSSEC(Algorithms)
C00159 00017 . SSSEC(Domain/Range)
C00172 00018 . SSSEC(Worth)
C00181 00019 . SSSEC(Interest)
C00195 00020 . SSSEC(Suggest)
C00204 00021 . SSSEC(Fillin/Check)
C00215 00022 . SSSEC(Other Facets which were Considered)
C00222 00023 .SSEC(AM's Starting Concepts)
C00224 00024 . SSSEC(Diagram of Initial Concepts)
C00228 00025 . SSSEC(Summary of Initial Concepts)
C00255 00026 . SSSEC(Rationale behind Choice of Concepts)
C00263 ENDMK
C⊗;
.NSECP(AM's Concepts)
.if false then start;
.BEGIN TURN ON "{}"
This chapter contains material about AM's anatomy.
After a brief overview, we'll look in detail at the way concepts are
represented (Section {SECNUM}.2). This includes a discussion of each
kind of facet a concept may possess. Wedged in among the
implementation details and formats are a horde of tiny ideas; they
should be useful to anyone contemplating working on a system similar
in design to AM.
The chapter closes by sketching all the knowledge
AM starts with.
The concepts will be diagrammed, and will also have a brief description,
sufficient for the
reader to follow later chapters without trouble.
.if false then start;
Instead of using up a large number of
pages for an unreadable listing of all of the specific information initially
supplied ⊗4re⊗* each concept, such complete coverage is relegated to Appendix
{[2] ALLCON}.1. $$
That appendix lists each concept, giving a condensed
listing of the facts initially given (by the author) to AM about each facet of
that concept. This material is
translated from LISP into English and standard math notation.
The appendix is preceded by an alphabetical index of the concepts and the
page number on which they are presented. That index is on page {[3]ENDINDEXCP}.
Some unmodified "concepts" -- still in LISP -- are displayed in
Appendix {[2] CONS}.{[3]CONSEC}. $
.end;
The next chapter starts on page {[3]R1PAGE}.$$Though devoid of theoretical
significance, that sentence has alas proved of high empirical value. $
.END;
.end;
.KNOWL: SECNUM ;
.SSEC(Motivation and Overview)
Each concept consists merely of a bundle of facets. The facets
represent the different aspects of each concept, the kinds of
questions one might want to ask about the concept:
.B48
How valuable is this concept?
What is its definition?
If it's an operation, what is legally in its domain?
What are some generalizations of this concept?
How can you separate the interesting instances of this concept from
the dull ones?
etc.
.E
Since each concept represents a mathematical entity, the kinds of questions
one might ask are fairly constant from concept to concept. This set
of questions might change somewhat for a new domain of concept.
One "natural" representation for a concept in LISP is as a
set of attribute/value pairs. That is, each concept is maintained as
an atom with a property list. The names of the properties (Worth,
Definitions, Domain/Range, Generalizations, Interestingness, etc.)
correspond to the questions above, and the value stored under
property F of atom C is simply the value of the F-facet of the C-concept.
This value can also be viewed as the answer which expert C would give, if asked
question F. Or, it can be viewed as the
contents of slot F of frame C.
. SSSEC(A Glimpse of a Typical Concept)
As an example, here is a stylized rendition of the SETS concept. This
is a concept which is meant to correspond to the notion of a set of
elements.
.if false then start;
The format P: v↓1,v↓2,... is used to indicate that the
value of property P is the list v↓1,v↓2,... That is, the concept Sets
has entries v↓1,v↓2,... for its facet P.
.end;
For example, according to
the box below, "Singleton" is one entry on the Specializations facet
of Sets -- i.e., singletons are specific kinds of sets..
.if false then begin;
I shall not digress here to explain each of these entries -- and what
are apparently omissions. Such things will be done later in this
chapter$$ The individual facets will be discussed one at a time. This
particular concept is shown at an intermediate state of being filled
in. Although several facets are blank, many are filled in which were
initially empty (e.g., Examples). The reader wishing to see what
this concept was like at the time that AM started up should turn
ahead to page {[3]SETCON} (inside Appendix {[2] ALLCON}).
$. For now,
just glance at it to get the flavor of what a concept is like.
.end;
.WBOX(10,11)
MBOX Name(s): Set, Class, Collection $
MBOX Definitions: $
MBOX Recursive: λ (S) [S=α{α} or Set.Definition (Remove(Any-member(S),S))] $
MBOX Recursive quick: λ (S) [S=α{α} or Set.Definition (CDR(S))] $
MBOX Quick: λ (S) [Match S with α{...α} ] $
MBOX Specializations: Empty-set, Nonempty-set, Set-of-structures, Singleton $
MBOX Generalizations: Unordered-Structure, No-multiple-elements-Structure $
MBOX Examples: $
MBOX Typical: {{}}, {A}, {A,B}, {3} $
MBOX Barely: {}, {A, B, {C, { { { A, C, (3,3,3,9), <4,1,A,{B},A>}}}}} $
MBOX Not-quite: {A,A}, (), {B,A} $
MBOX Foible: <4,1,A,1> $
MBOX Conjec's: All unordered-structures are sets. $
MBOX Intu's: $
MBOX Geometric: Venn diagram. α{See [Venn 89], or [Skemp 71].α} $
MBOX Analogs: bag, list, oset $
MBOX Worth: 600 $
MBOX View: $
MBOX Predicate: λ (P) {xεDomain(P) | P(x)} $
MBOX Structure: λ (S) Enclose-in-braces(Sort(Remove-multiple-elements(S))) $
MBOX Suggest: If P is an interesting predicate over X, consider {xεX | P(x)}. $
MBOX In-domain-of: Union, Intersection, Set-difference, Set-equality, Subset, Member $
MBOX In-range-of: Union, Intersection, Set-difference, Satisfying $
.EBOX
.GROUP
To decipher the Definitions facet, there are a few things you must know.
An expression of the form "(λ (x) E)" is called a Lambda expression
after Church$$
Before and during Church, it's called a function. See [Church 41]. $,
and may be considered an executable procedure.
it accepts one argument, binds the variable "x"
to the value of that argument, and then
evaluates "E" (which is probably some expression involving the variable x).
For example, "(λ (x) (x+5))" is a function which
adds 5 to any number; if given the argument 3, this lambda expression will return
the value 8.
.APART
The second thing you must know is that facet F of concept C will occasionally
be abbreviated as C.F. In those cases where F is "executable", the notation
C.F will refer to applying the corresponding function.
So the first entry in the Definitions facet is recursive because it contains
an embedded call on the function Set.Definition.
Notice that we are implying that the ⊗4name⊗*
of that lambda expression itself is "Set.Definition".
There are some unusual implications of this: since there are three separate but
equivalent definitions, AM may choose whichever one it wants when it recurs.
AM can choose one via a random selection scheme, or always try to recur into the
same definition as it was just in, or perhaps suit its choice to the form of
the argument at the moment.
.ONCE TURN ON "{}"
For example, one definition might be great for arguments
of size 10 or less, but slow for bigger ones, and another definition might be
mediocre for all size arguments; then AM should
use the mediocre definition over and over again, until the
argument becomes small enough,
and from then on recur only into the fast definition.
Although AM embodies this "smart" scheme, the little comments necessary to
see how it does so have be excised from the version shown above in the box.
This will be explained later in this chapter, on page {[3] RECURPAGE}.
All concepts possess executable definitions, though not necessarily effective
ones. They each have a LISP predicate, but that predicate is not guaranteed
to terminate. Notice that the definitions for Sets are all definitions of
finite sets.
. SSSEC(The main constraint: Fixed set of facets)
One important constraint on the representation is that the set of
facets be fixed for all the concepts.
An additional constraint is that this set of facets not grow, that it be
fixed once and for all.
So there is one fixed, universal list
of two dozen types of facets. Any facet of any concept
⊗4must⊗* have one of those standard names. All concepts which have
some examples must store them as entries on a facet called Examples;
they can't call them Instances, or Cases, or G00037's. This
constraint is known as the "⊗6Beings⊗* constraint"$$ See [Lenat 75b].
Historically, each concept module was called a "BEING". $, and has
three important consequences:
.SKIP 1 BN
λλ OUTLINE: First, it provides a nice, distributed, universal
framework on which to display all that is known about a given
concept.
AM can instantly tell what facets are not yet
filled in for any given concept, and this will in turn suggest new
tasks to perform. In other words, this constraint helps define the
"space" which AM must explore, and makes it obvious what parts of
each concept have and have not yet been investigated.
λλ STRUCTURE: The constraint specifies that there be a ⊗4set⊗* of
facets, not just one. This set was made large enough that all the
efficiency advantages of a "structured" representation are preserved
(unlike totally uniform representations, e.g. pure production systems
with simple memories as data structures, or predicate calculus).
λλ UNIFORMITY: When AM wishes a piece of information, it must ask a
concept a "question" -- i.e., mention a particular facet by name.
The benefit of the ⊗6Beings⊗* constraint is that there is a fixed,
small repertoire of questions it may ask, hence there will be
no long searching, no misunderstandings. This is the same advantage
that always accrues when everyone uses a common language.
.E
We shall illustrate the last two advantages by using the Sets concept
pictured in the box a couple pages ago. How does AM handle a task of
this form: "⊗6Check examples of Sets⊗*"? AM accesses the examples
facet of the Sets concept, and obtains a bunch of items which are all
probably sets. If any isn't a set, AM would like to make it one, if
that involves nothing difficult. AM locates all the generalizations
of Sets$$ by "rippling" upward from Sets, in the Genl direction$, and
comes up with the list <Sets, Unordered-Structures,
No-multiple-elements-Structures, Structures, Objects, Any-concept,
Anything>. Next, the "Check" facet of each of these is examined, and
all its heuristics are collected. For example, the Check facet of
the No-multiple-elements-Structures concept contains the following
entry: "Eliminate multiple occurrences of each element" (of course
this is present not as an English sentence but rather as a little
LISP function). So even though Sets has no entries for its Check
facet, several little functions will be gathered up by the rippling
process. Each potential set would be subjected to all those checks,
and might be modified or discarded as a result.
There is enough "structure" around to keep the heuristic rules
relevant to this task isolated from very irrelevant rules, and there
is enough "uniformity" to make finding those rules very easy.
The same rippling would be done to find predicates which tell whether
a set is interesting or dull. For example, one entry on the
Interestingness facet of the Structure concept says that a structure
is interesting if all pairs of members satisfy the same rare
predicate P(x,y) [for any such P]. So a set, all pairs of whose
members satisfy "Equality," would be considered interesting. In fact,
every Singleton is an interesting ⊗4Structure⊗* for just that reason.
A singleton might be an interesting ⊗4Anything⊗* because it takes only
a few characters to type it out (thereby satisfying a criterion on
Anything.Interest).
To locate all the specializations of Sets, the rippling would go in
the opposite direction. For example, one of the entries on the
Specializations facet of Sets is Set-of-structures; one if ⊗4its⊗*
Specialization entries is Set-of-sets. So this latter concept will be
caught in the net when rippling away from Sets in the Specializations
direction.
If AM wants lots of examples of sets, it has only to ripple in the
Specializations direction, gathering Examples of each concept it
encounters. Examples of Sets-of-sets (like this one: {{A},{{C,D}}})
will be caught in this way, as will examples of Sets-of-numbers (like
this one: {1,4,5}), because two specializations of Sets are
Sets-of-Sets and Sets-of-Numbers$$ We are assuming that AM has run
for some time, and already discovered Numbers, and already defined
Sets-of-Numbers. $.
In addition to the three main reasons for keeping the set of facets the same
for all the concepts (see previous page), we claimed there were also reasons
for keeping that set
fixed once and for all.
Why not dynamically enlarge it?
To add a new facet, its value has to be filled in for lots of concepts.
How could AM develop the huge body of heuristics needed to guide such
filling-in and checking activities? Also, the number of facets is small
to begin with because people don't seem to use more than a few tens of
such "properties" in classifying knowledge about a concept$$ This data
is gathered from introspection by myself and a few others, and should probably
be tested by performing some psychological experiments. $.
If the viability of AM seemed to depend on this ability, I would have worked
on it. AM got along fine without being able to enlarge its set of facets, so
no time was ever spent on that problem.
I leave it as a challenging, ambitious "open research problem".
. SSSEC(BEINGs Representation of Knowledge)
Before discussing each facet in detail, let's interject a brief
historic digression, to explain the origins of this modular
representation scheme.
The ideas arose in an automatic programming context, while working
out a solution to the problem of constructing a computer system
capable of synthesizing a simple concept-discrimination program
(similar to [Winston 70]). The scenario envisioned was one of mutual
cooperation among a group of a hundred or so experts, each a
specialist in some minute detail of coding, concept formation,
debugging, communicating, etc. Each expert was modelled by one
module, one BEING. Each BEING had the same kinds of slots (parts,
facets), and each slot was interpreted as a ⊗4question⊗* which that
BEING could answer. The community of experts carried on a
round-table discussion of a programming task which was specified by a
human user. Eventually, by cooperating and answering each other's
questions, they hammered out the program he desired. See [Lenat
75b] for details.
The final system, called PUP6, did actually synthesize several large
LISP programs, including many variants of the concept-learning
program. This is described in detail in [Lenat 75a]. Unfortunately,
PUP6 had virtually no natural language ability and was therefore
unusable by an untrained human. Its modal output was "⊗4Eh?⊗*".
The search for a new problem domain where this communication
difficulty wouldn't be so severe led to consideration of elementary
mathematics.
The other main defect of PUP6 was its narrowness, the small range of
`target' programs which could be synthesized. PUP6 had been designed
with just one target in mind, and almost all it could do was to hit
that target. The second constraint on the new task domain was then
one of having a non-specific target, a very broad or diffuse goal.
This pointed to an automated researcher, rather than a
problem-solver.
These two constraints then were (i) elementary math, because of
communication ease, and (ii) self-guided exploration, because of the
danger of too specific a goal. Together, they directed the author to
an investigation which ultimately resulted in the AM project.
.SSEC(Facets)
How ⊗4is⊗* each concept
represented?
Without claiming that this is the "best" or preferred scheme, this section
will treat in detail AM's representation of this knowledge.
.FACETSSEC: SSECNUM;
.FACETPAGE: PAGE;
We have seen that the representation of a concept can loosely be
described as a collection of facet/value pairs, where the facets are
drawn from a fixed set of about 25 total possible facets.
.if false then start;
The facets break down into three categories:
.BN
λλ Facets which relate this concept C to some other one(s):
Generalizations, Specializations, Examples, Isa's, In-domain-of,
In-range-of, Views, Intu's, Analogies, Conjec's
λλ Facets which contain information intensive to this concept C:
Definitions, Algorithms, Domain/Range, Worth, Interest
λλ Sub-facets, containing heuristics, which can be tacked onto facets from either
group above. These include: Suggest, Fillin, Check
.E
.end;
Some facets come in several flavors (e.g., there are really four
separate facets -- not just one -- which point to Examples: boundary,
typical, just-barely-failing, foibles).
.GROUP
This section will cover each facet in turn. Let's begin by listing
each of them. For a change of pace, we'll show a typical question
that each one might answer about concept C:$$ In this discussion, "C"
represents the name of the concept whose facet is being discussed,
and may be read "the given concept". $
.SKIP 1 BN
Name: What shall we call C when communicating with the user?
.FACETPAG2: PAGE;
Generalizations: Which other concepts have less restrictive definitions than C?
Specializations: Which concepts satisfy C's definition plus some additional
constraints?
Examples: What are some things that satisfy C's definition?
Isa's: Which concepts' definitions does C itself satisfy?$$ Notice that C will
therefore be an example of each member of Isa's(C). $
In-domain-of: Which operations can be performed on C's?
In-range-of: Which operations result in values which are C's?
Views: How can we view some other kind of entity as if it were a C?
Intu's: What is an abstract, analogic representation for C?
Analogies: Are there similar (though formally unrelated) concepts?
Conjec's: What are some potential theorems involving C?
Definitions: How can we tell if x is an example of C?
Algorithms: How can we execute the operation C on a given argument?
Domain/Range: What kinds of arguments can operation C be executed on? What kinds of
values will it return?
Worth: How valuable is C? (overall, aesthetic, utility, etc.)
Interestingness: What special features make a C especially interesting?
.E
In addition, each facet F of concept C can possess a few little subfacets which
contain heuristics for dealing with that facet of C's:
.bn SKIP 1
C.F.Fillin: How can entries on C.F be filled in?
These heuristics get called on when the current task is ⊗6"Fillin
facet F of concept X"⊗*, where X is a C.
C.F.Check: How can potential entries on C.F be checked and patched up?
C.F.Suggest: If AM gets bogged down, what are some new tasks (related to C.F)
it might consider?
.E; APART;
.if false then start;
.SS1←SSECNUM+1;
.ONCE TURN ON "{}"
We'll now begin delving into the syntax and semantics of each facet,
one by one. Future chapters will not depend on this material. The
reader may wish to skip to Section {SECNUM}.{SS1} (page {[3]CDIAG}).
.end;
. SSSEC(Generalizations/Specializations)
.QQ
Generalization makes possible conscious, controlled, and accurate accomodation
of one's existing schemas, not only in response to the demands for assimilation
of new situations as they are encountered, but ↓_ahead_↓ of these demands,
seeking or creating new examples to fit the enlarged concept.
-- Skemp
.ESS
We say concept A "⊗4is a generalization of⊗*" concept B iff
every example of B is an example of A. Equivalently, this is true iff
the definition of B can be phrased as "λ (x) [A.Defn(x) and P(x)]";
that is, for x to satisfy B's definition, it must satisfy A's definition plus
some additional predicate P.
The Generalizations facet of concept C will be abbreviated as C.Genl.
C.Genl does not contain ⊗4all⊗* generalizations of
C; rather, just the "immediate" ones. More formally, if A is a generalization
of B, and B of C, then C.Genl will ⊗4not⊗* contain a pointer to A.
Instead, C will point to B
.GROUP
Here are the recursive equations which permit a search process to quickly find
all generalizations or specializations of a given concept X:
.B816
Generalizations(X) = Genl↑*(X) = α{Xα} ∪ Generalizations(X.Genl)
Specializations(X) = Spec↑*(X) = α{Xα} ∪ Specializations(X.Spec)
.E APART GROUP;
For the reader's convenience, here are the
similar equations, presented elsewhere in the text,
for finding all examples of -- and Isa's of -- X:
.B816
Examples(X) = Spec↑*(Exs(Spec↑*(X)))
Isa's(X) = Genl↑*(Isa(Genl↑*(X)))
.E APART GROUP;
The format of the Generalizations facet is quite simple: it is a list of
concept names. The Generalizations facet for Odd-primes might be:
.B816
(Odd-numbers Primes)
.E APART GROUP
Here is a small diagram representing generalization relationships. The lines
drawn represent the pointers found in the Genl facets of these concepts:
.B0 INDENT 25
Object
\
\
\
\
\
\
Number
/ \
/ \
/ \
/ \
/ \
/ \
Odd-numbers Primes
\ / \
\ / \
\ / \
\ / \
\ / \
\ / \
Odd-primes Even-primes
\
\
\
\
\
\
Mersenne-primes
.E
Each of those lines represents an arrow which slants upwards, indicating a Genl link.
For example, we see that the Generalizations facet of Odd-primes contains
pointers to both Odd-numbers and to Primes.
There is no pointer from Odd-primes upward to Number, because
there is an "intermediate" concept (namely, Primes).
There is no pointer from Mersenne-primes to Object, since a chain of
intermediate concepts links them.
.APART
The reason for these strange constraints is so that the total number of links
can be minimized. There is no harm if a few redundant ones sneak in.
In fact, frequently-used paths are granted the status of single links, as we
shall soon see.
We've been talking about both Specializations and Generalizations as if they were
very similar to each other. It's time to make that more explicit:
Specializations are the converse of Generalizations. The format is the same, and
(hopefully) A is an entry on B's Specializations facet iff B is an entry on
A's Generalizations facet.
The uses of these two facets are many:
.BN
.TURN ON "{}"
λλ AM can sometimes establish independently that A is both a generalization and
a specialization of B; in that case, AM would like to
recognize that fact easily, so it can
conjecture that A and B specify
equivalent concepts. Such coincidences are easily detected as ⊗4↓_cycles_↓⊗* in the
Genl (or Spec) graph.
In these cases, AM may physically merge A and B
(and all the other concepts in the cycle)
into one concept.
λλ Sometimes, AM wants to assemble a list of all specializations (or
generalizations) of X, so that
it can test whether some statement which is just barely true (or false) for X
will hold for any of those specializations of X.
λλ Sometimes, the list of generalizations is used to assemble a list of
isa's; the list of specializations helps assemble a list of examples.
λλ A common and crucial use of the list of generalizations is to locate all the
heuristic rules which are relevant to a given concept. Typically, the relevant
rules are those tacked onto Isa's of that concept, and the list of Isa's is built up
from the list of generalizations of that concept.
This was also mentioned on page {[3] GENLSPEC}.
λλ To incorporate new knowledge. If AM learns, conjectures, etc. that A is a
specialization of B, then all the machinery (all the theorems, algorithms, etc.)
for B become available for working with A.
.E
.TRICK: PAGE;
Here is a little trick that
deserves a couple paragraphs of its own. AM stores the answers to common questions
(like "What are ⊗4all⊗* the specializations of Operation") explicitly,
by intentionally permitting redundant links to be maintained.
If two requests arrive closely in time, to test whether A is a generalization
of B, then the result is stored by adding "A"
as an entry on the Generalizations facet of
B, and adding "B" as a new entry on
the Specializations facet of A.
The slight extra space is more than recompensed in cpu time saved.
If the result were False (A turned out not to be a generalization of B) then the
links would specify that finding explicitly,
so that the next request would not generate a long search again.
Such failures are recorded on two additional facets: Genl-not and Spec-not.
Since most concept pairs A/B are related by Spec-not and by Genl-not,
the only entries which get recorded here are the ones which were frequently
called for by AM. If space ever gets tight, all such facets can be
wiped clean with no permanent damage done.
These two "shadow" facets (Genl-not and Spec-not) are not useful or interesting
in their own right.
If AM ever wished to know all
the concepts which are ⊗4not⊗* generalizations of C, the fastest way would
be to take the set-difference of all concepts and Generalizations(C).
Since they are quite incomplete, Genl-not and Spec-not are used more like a cache
memory: they save time whenever they are applicable, and don't really cost
much when they aren't applicable.
.if false then start;
Because of their superfluity, these two facets will not be mentioned again.
I only mentioned them above because they do greatly speed up AM's execution
time, and because they may have some psychological analog.
.end;
. SSSEC(Examples/Isa's)
.QQ
Usually, to show that a definition implies no contradiction, we
proceed ↓_by example_↓, we try to make an ↓_example_↓ of a thing
satisfying the definition. We wish to define a notion A, and we say
that, by definition, an A is anything for which certain postulates
are true. If we can demonstrate directly that all these postulates are
true of a certain object B, the definition will be justified; the
object B will be an ↓_example_↓ of an A.
-- Poincare'
.ESS
.ONCE TURN ON "{}"
Following Poincare', we say "⊗4concept A is an example of concept B⊗*" iff
A satisfies B's definition.$$
What does this mean? B.Defn is a Lisp predicate, a Lambda expression.
If it is fed A as its argument, and it returns True, we say that
A is a B, or that A satisfies B's definition. If B.Defn returns NIL,
we say that A is not a B, or that A fails B's definition. If B.Defn
runs out of time before returning a T/NIL value, there is no definite
statement of this form we can make.
$ Equivalently, we say that "⊗4A isa B⊗*".
It would be legal (in that situation) for "A" to be an entry on
B.Exs (the Examples facet of concept B) and for "B" to be an entry on
A.Isa (the Isa's facet of concept A).
Some earlier mention of the
Examples and Isa's facets can be seen in Chapter {[2]HEURS}, page
{[3]EXISA}.
The Examples facet of C does not contain ⊗4all⊗* examples of
C; rather, just the "immediate" ones.
The examples facet of Numbers will not contain "11" since it
is contained in the examples facet of Odd-primes.
A "rippling" procedure is used to acquire a list of all examples of a given
concept. The basic equation is:
.B816
Examples(x) = Specializations(Exs(Specializations(x)))
.E
.ONCE TURN ON "{}"
where Exs(x) is the contents of the examples facet of x.
Examples(x) represents the final list of all known items which satisfy
the definition of X. Examples(x) thus must include Exs(x).
Specializations(x) might be more regularly written Spec↑*(x). That is,
all members of x.Spec, all members of ⊗4their⊗* Spec facet, etc.
Note the similarity of this to the formula for Isa's(x), given on page {[3]GIGPAGE}.
We could also write the above equation as follows:
.B816
Examples(x) = Spec↑*(Exs(Spec↑*(x)))
.E
As an illustration, we shall show how AM would recognize that "3" is an example
of Object:
.B0 INDENT 25
Object
\
\
\
\
\
\
Number
/ \
/ \
/ \
/ \
/ \
/ \
Odd-numbers Primes
\ /
\ /
\ /
\ /
\ /
\ /
Odd-primes
\
\
\
\
\
\
Mersenne-primes
α⊗
α⊗
α⊗
3
.E
As the graph above shows, AM would ripple in the Spec direction 4 times,
moving from Object all the way to Mersenne-primes; then descend once in the
Exs direction, to reach "3"; then ripple 0 more times in the Spec direction.
Thus "3" is seen to be an example of Object, according to the above formula.
Similarly, we see that "3" is also an example of Number, of Primes, of Odd-number,
of Odd-primes, and of course an example of Mersenne-primes.
As with Generalizations/Specializations, the reasons behind the
incomplete pointer structure is simply to save space, and to minimize the
difficulty of updating the graph structure whenever new links are found.
Suppose a new Mersenne prime$$
"Mersenne prime", without a hyphen, refers to a number satisfying certain
properties.
"Mersenne-primes", with a hyphen, refers to one specific AM concept,
a data structure with facets. Each Mersenne prime is an example of the
concept Mersenne-primes. $
is computed. Wouldn't it be nice simply to add a
single entry to the Exs facet of Mersenne-primes, rather than to have to update the
Exs pointers from a dozen concepts?
There is no harm if a few redundant links sneak in.
.if false then start;
In fact, frequently-used paths are granted the status of single links.
If two requests arrive closely in time, to test whether A isa
B, then the result is stored as an entry on the Isa facet of
A, and the Exs facet of B. If the result were False, then the
links would specify that, so that the next request would not generate a long search.
In fact, there is a separate facet called Exs-not, and one called Isa-not.
These two shadowy facets are quite analogous to the unmentionable facets
"Genl-not" and "Spec-not", discussed in the previous subsection.
.end;
"Isa's" is the converse of "Examples". The format is the same, and
(if A and B are both concepts) A is an entry on B.Isa iff B is an entry on
A.Exs. In other words, A is a member of Examples(B) iff B is a member of
Isa's(A).
.if false then start;
Due to an ugly lack of standardization, non-concepts are allowed to
exist. Thus, "3" is an example of Primes, but is not itself a concept.
Examples of X sometimes are concepts, of course: "Intersect-o-Intersect" is an
example of Compose-with-self.
And Isa's(x) are always concepts.
The highest level concept is called "Anything". Its definition is the
atom T. That is, "λ(x) T". This high-level concept can claim everything as
its examples.
.end;
The ⊗4uses⊗* of the Exs/Isa's facets are similar to those for Genl/Spec
(see previous subsection).
Their formats are quite a bit more complicated than
the Genl/Spec facets' formats, when we finally get to the
implementation level, however.
There are really a cluster of different facets all related to Examples:
.SKIP 1 BN
λλ TYPICAL: This is a list of average examples. Care must be taken to include a wide
spectrum of allowable kinds of examples.
For "Sets", these would include sets of varying
size, nesting, complexity, type of elements, etc.
λλ BOUNDARY: Items which just barely pass the definition of this concept. This might
include items which satisfy the base step of a recursive definition, or items which
were intuitively believed to be ⊗4non⊗*-examples of the concept.
For "Sets", this
might include the empty set.
λλ BOUNDARY-NOT: Items which just barely fail the definition. This might include an
item which had to be slightly modified during checking, like α{A,B,Aα} becoming
α{A,Bα}.
λλ FOIBLES: Total failures. Items which are completely against the grain of this
concept. For "Sets", this might include the operation "Compose".
λλ NOT: This is the "cache" trick used to store the answers to frequently-asked
questions. If AM frequently wants to know whether X is an example of Y, and
the answer is ⊗4No⊗*, then much time can be saved by adding X as an entry to the
Exs-not facet of Y.
.E
An individual item on these facets may just be a concept name, or it may be
more complicated.
In the case of an operation, it is an item of the form <a↓1a↓2...→v>; i.e., actual
arguments and the value returned. In the case of objects, it is an object of
that form. An Exs facet of the concept Sets might contain {a} as one entry.
Here is a more detailed illustration. Consider the
Examples facet of Set-union. It might appear thus:
.GROUP B816; TURN ON "{}\"; TABS 25;
TYPICAL: α{Aα}∪α{A,Bα}→α{A,Bα};
.ONCE INDENT 15;
α{A,Bα}∪α{A,Bα}→α{A,Bα};
.ONCE INDENT 15;
α{A,<3,4,3>,α{A,Bα}α}∪α{3,Aα}→α{A,<3,4,3>,α{A,Bα},3α}.
BOUNDARY: α{α}∪X→X $$
Actually, AM is not quite smart enough to use the variable X as shown in the
boundary examples. It would simply store a few instances of this general rule, plus
have an entry of the form <Equivalent: Identity(X) and Set-union(X,α{α})> on the
Exs facet of Conjectures.
Notice that because of the asymmetric way Set-union was defined,
only one lopsided boundary example was found. If another definition were supplied,
the converse kind of boundary examples would be found. $
BOUNDARY-NOT: α{A,Bα}∪α{A,Cα}→α{A,B,A,Cα};
.ONCE INDENT 25;
α{A,B,C,Dα}∪α{E,F,G,H,I,Jα}→α{A,B,C,E,F,G,H,I,Jα}
FOIBLES: <2,A,2>
NOT: no entries
.E; APART;
The format for Isa's are much simpler:
there are only two kinds of links, and they're each merely a
list of concept names.
Here is the Isa facet of Set-union:
.B816 GROUP
ISA: (Operation$$ This entry is redundant. $ Domain=Range-op)
ISA-NOT: (Structure Composition Predicate)
.E
At some time, some rule asked whether Set-union ↓_isa_↓ Composition. As a result,
the negative response was recorded by adding "Composition" to the Isa-not
facet of Set-union, and adding "Set-union" to the Exs-not subfacet of the
Examples facet of the concept Composition
(indicating that Set-union was definitely not an
example of Composition, yet there was no reason to consider it a foible).
. SSSEC(In-Domain-of/In-Range-of)
.COMMENT: WARNING: DON'T CENTER!!!;
We shall say that A is in the domain of B (written "A In-dom-of B")
iff
.BN
λλ A and B are concepts
λλ B isa Operation
λλ A is equal to (or at least a
specialization of) one of the domain components of the operation B. That is,
B can be executed using any example of A as one of its arguments.
.if false then start;
More formally, we can say that this occurs whenever
some entry on the Domain/range facet of B has the form <D↓1
D↓2... D↓i → R> with some D↓j a member of Generalizations(A). Then A
is a specialization of some domain component of some entry on
B.Domain/range.
.end;
.E
.if false then start;
For example, Odd-perfect-squares is In-dom-of Add, since
Odd-perfect-squares is a specialization of Numbers,
and Numbers is one component of the following entry which is located on
Add.Domain/range: <Numbers Numbers → Numbers>.
Since Odd-perfect-squares is a specialization of Numbers,
the operation `Add' can be executed using any example of Odd-perfect-squares
as its argument.
As another
example, Odd-perfect-squares is also In-dom-of Set-insert,
one of whose Domain/range
entries is <Anything Sets → Sets>. This is because
Odd-perfect-squares is a specialization of Anything.
So Set-insert is executed on two arguments, and the first argument can be
any example of Odd-perfect-squares (the second argument must be an example of
Sets).$$ Since Odd-perfect-squares is more closely related to Numbers than to
the concept Anything
(half as many Genl links away), AM expects that restricting Add to Odd-perfect-squares
will probably yield a more promising new operation than restricting Set-insert
to only insert odd perfect squares into sets. $
Although it can be recomputed very easily, we may wish to record the
fact that A In-dom-of B by adding the entry "B" to the In-dom-of
facet of A. AM may even wish to add this new entry to the
Domain/range facet of B (where A is a specialization of the j↑t↑h
domain component of B):
.ONCE PREFACE 0
< D↓1 D↓2... D↓j↓-↓1 A D↓j↓+↓1... D↓i → R>.
The two examples given above would produce new domain/range entries of
<Odd-perfect-squares Numbers → Numbers> for Add, and <Odd-perfect-squares
Sets → Sets> for Set-insert.
.end;
The semantic content of "In-dom-of" is: what can be done to
any example of
a given
concept C? Given an example of concept C, what operations can be
run on that thing? E.g.,
"Primes In-dom-of Squaring" tells us that we can apply the operation
Squaring to any particular prime number we wish.
Let us now turn from In-dom-of to the related facet In-ran-of.
We say that concept A is in the range of B iff B is an Activity
.if false then start;
[ i.e., iff B isa Active, iff BεExamples(Active), iff Active.Defn(B)=True.
Actually, since the range of Predicates is merely α{T,Fα}, we may as well assume that
B is an operation, not a predicate. This is in fact assumed, in the text and in
the actual AM system. ]
.end;
and A is a specialization of the range of B.
.if false then start;
More precisely,
we can say that "A In-ran-of B" iff
.BN
λλ A and B are concepts
λλ B isa Operation (i.e., B is an example of the concept "Operation")
λλ Some entry on the Domain/range facet of B has the form <D↓1
D↓2... D↓i → R> with R a generalization of A.
.E
For example, Odd-perfect-squares is In-ran-of Squaring, since (1) both of
those are concepts, (2) Squaring is an operation, (3) one of its Domain/range
entries is <Numbers→Perf-squares>, and
Perf-squares is a generalization of Odd-perfect-squares$$ Why? Because
Generalizations(Odd-perfect-squares) is the set of concepts
α{Odd-numbers Perf-squares Numbers Objects Any-concept Anythingα},
hence contains Perf-squares.
So Perf-squares is a generalization of Odd-perfect-squares. $.
Here is what the In-ran-of facet of Odd-perfect-squares might look
like:
.B816
(Squaring Add TIMES Maximum Minimum Cubing)
.E
Each of these operations will -- at least
sometimes -- produce an odd perfect square
as its result.
.end;
Semantically, the In-ran-of relation between A and B means that one
might be able to produce examples of
A by running operation B.
Aha!
This is a potential mechanism for finding examples of a concept A.
All you need do is get hold of In-ran-of(A), and run each of those
operations. Even more expeditious is to examine the Examples facets
of each of those operations, for already-run examples whose values
should be tested using A.Defn, to see if they are examples of A's.
AM relies on this in times of high motivation; it is too "blind" a
method to use heavily all the time.
This facet is also useful for generating situations to investigate.
Suppose that the Domain/range facet of Doubling contains only one
entry: < Numbers → Numbers >. Then syntactically, Odd-numbers is in the
range of Doubling. Eventually a heuristic rule may have AM spend some
time looking for an example of Doubling, where the result was an odd
number. If none is quickly found, AM conjectures that it ⊗4never⊗* will be
found. Since one definition of Odd-number(x) is "Number(x) and
Not(Even-number(x))", the only non-odd numbers are even numbers. So
AM will increment the Domain/range facet of Doubling with the entry
<Numbers→Even-numbers>, and remove the old entry. Thus Odd-numbers
will no longer be In-dom-of Doubling. AM can of course chance upon
this conjecture in a more positive way, by noticing that all known
examples of Doubling have results which are examples of Even-numbers.$$ This
positive approach is in fact the way AM noticed this particular relationship. $.
.XGENLINES←XGENLINES-1;
.SEND FOOT ⊂ TURN ON "[]{" SELECT 7; SPACING 0; PREFACE 0; INDENT 0,10
⊗A6⊗* Wrong. That was an exponent, not a footnote!
.BREAK ⊃
A more productive result is suggested by examining the cases where
Odd-perfect-squares are the result of cubing. The smallest such odd
numbers are 1, 729, and 15625. In general, these numbers are all those of
the form (2n+1)↑6. How could AM notice such an awkward relationship?
The general question to ask, when A In-ran-of B,
is "What is the set of domain items whose values (under the operation
B) are A's?" In case the answer is "All" or "None", some special
modifications can be made to the Domain/range facets and In-dom-of,
In-ran-of facets of various concepts, and a new conjecture can be
printed. In other cases, a new concept might get created,
representing precisely the set of all arguments to B which yield
values in A. If you will, this is the inverse image of A, under
operation B. In the case of B a predicate, this might be the set of
all arguments which satisfy the predicate.
In the case of B=Cubing
and A=Odd-perfect-squares, the heuristic mentioned above will have
AM create a new concept:
the inverse image of Odd-perfect-squares under the operation of Cubing.
That is, find numbers whose cubes are Odd-perfect-squares.
It is quickly noticed that such numbers are precisely the set of
Odd-perfect-squares themselves! So
The Domain/range facet of Cubing might get this new entry:
<Odd-perfect-squares → Odd-perfect-squares>.
But not all squares can be reached by cubing, only a few of them can.
AM will notice this, and
the new range would then be isolated and might be renamed
by the user "Perfect-sixth-powers". Note that all this
was brought on by examining the In-ran-of facet of
Odd-perfect-squares. "Cubing" was just one of the seven
entries there. There are six more stories to tell in this
tiny nook of AM's activities.
How exactly does AM go about gathering the In-ran-of and In-dom-of
lists? Given a concept C, AM can scan down the global tree of operations
(the Exs and Spec links below the concept `Active').
For if C is not In-dom-of F, it certainly won't be In-dom-of any
specialization of F. Similarly, if it can't be produced by F, it
won't be produced by any specialization of F. If you can't get x
using Doubling you'll never get it by Quadrupling. So AM simply ripples
around, as usual. The precise code for this algorithm is of little
interest. There are not that many operations, and it is cheap to
tell whether X is a specialization of a given concept, so even an
exhaustive search wouldn't be prohibitive. Finally, recall that such
a search is not done all the time. It will be done initially,
perhaps, but after that the In-dom-of and In-ran-of networks will
only need slight updating now and then.
. SSSEC(Views)
Often, two concepts A and B will be inequivalent, yet there will be a "natural"
bijection between one and (a subset of) the other.
For example, consider a finite set S of atoms, and consider the
set of all its subsets, 2↑S,
also called the ⊗4power set⊗* of S.
Now S is a member of, but not a ⊗4subset⊗* of, 2↑S
(e.g., if S={x,y,...}, then x is not a member of 2↑S).
On the other hand, we can identify or view
S as a subset by the mapping v→{v}. Then S is associated with the following
subset of 2↑S: { {x}, {y},... }. Why would we want to do this? Well, it shows
that S is identified with a ⊗4proper⊗* subset of 2↑S, and indicates that S has
a lower cardinality (remember: all sets are finite).
As another example, most of us would agree that the set {x, {y}, z} can be
associated with the following bag: (x, {y}, z). Each of them can be viewed as
the other. Sometimes such a viewing is not
perfectly natural, or isn't
really a bijection: how could
the bag (2, 2, 3) be viewed as a set? Is {2,3} better or worse than
{2,{2},3)?
The View facet of a concept C describes how to view instances of another concept D
as if they were C's. For example, this entry on the View facet
of Sets explains how to view any given structure as if it were a Set:
.B816
Structure: λ (x) Enclose-in-braces(Sort(Remove-multiple-elements(x)))
.E
If given the list <z,a,c,a>, this little program would remove
multiple elements (leaving <z,a,c>), sort the structure
(making it <a,c,z>), and replace the "<...>" by "{...}", leaving the
final value as {a,c,z}. Note that this transformation is not 1-1; the
list <a,c,z> would get transformed into this same set.
On the other hand, it may be more useful than transforming
the original list into {z,{a,{c,{a}}}} which retains the ordering and
multiple element information.
Both of those transformations may be present as entries on the View
facet of Sets.
.if false then start;
As it turns out, the View facet of Sets actually contains only the following
information:
.B816
Structure: λ (x) Enclose-in-braces(x)
.E
Thus the Viewing will produce entities which are not quite sets. Eventually,
AM will get around to executing a task of the form "Check Examples of Sets",
and at that time the error will be corrected.
One generalization of Sets is No-multiple-elements-Structures, and one of its
entries under Examples.Check says to remove all multiple elements. Similarly,
Unordered-structures is a generalization of Sets, and one of its Examples.Check
subfacet entries
says to sort the structure. If either of these alters the structure, the old structure
is added to the Boundary-not subfacet (the `Just-barely-miss' kind) of
Examples facet of Sets.
The syntax of the View facet
of a concept C
is a list of entries; each entry specifies the name of
a concept, X, and a little program P. If it is desired to view an instance of
X as if it were a C, then program P is run on that X; the result is (hopefully)
a C. The programs P are opaque to AM; they must have no side effects and be quick.
Here is an entry on the View facet of Singleton:
.B816
Anything: λ (x) Set-insert(x, PHI)
.E
In other words, to view anything as a singleton set, just insert it into the
empty set. Note that this is also one way to view anything as a set.
.end;
As you've
no doubt guessed, there is a general formula explaining this:
.ONCE CENTER PREFACE 0 SELECT 6
Views(X) ≡ View(Specializations(X))
Thus, to find all the ways of viewing something as a C, AM ripples away from C
in the Spec direction, gathering all the View facets along the way.
All of their entries are valid entries for C.View as well.
.GROUP
In addition to these built-in ways of using the Views facets, some special
uses are made in individual heuristic rules.
Here is a heuristic rule which employs the Viewing facets of relevant concepts in
order to find some examples of a given concept C:
.B816
.ONCE INDENT 4
IF the current task is to Fill-in Examples of C,
and C has some entries on its View facet,
and one of those entries <X,P> indicates a concept X which has some known Examples,
.ONCE INDENT 4
THEN run the associated program P on each member of Examples(X),
and add the following task to the agenda: "Check Examples of C", for the
following reason: "Some very risky techniques were used to find examples of C",
and that reason's rating is computed as:
Average(Worth(X), ||the examples of C found in this manner||).
.E
.APART
Say the task selected from the agenda was "Fill-in Examples of Sets".
We saw that one entry on Sets.View was ⊗6Structure: λ(x) Enclose-in-braces(x)⊗*.
Thus it is of the form <X,P>, with X=Structure. The above heuristic rule will
trigger
if any examples of Structures are known. The rule will then use the
View facet of Sets to find some examples of Sets.
So AM will go off, gathering all the examples of structures.
Since Lists is a Specialization of
Structure, the computation of Examples(Structures) will eventually ripple
downwards and ask for Examples of Lists. If the Examples facet of Lists
contains the entry <z,a,c,a,a>, then this will be retrieved
as one of the members of Examples(Structure). The heuristic rule takes each such
member in turn, and
feeds it to Set.View's
little program P.
In this case, the program replaces the list brackets with set braces, thus converting
<z,a,c,a,a> to α{z,a,c,a,aα}.
In this manner, all the existing structures will be converted
into sets, to provide examples of sets.
After all such conversions take place, a great number
of potential examples of Sets will exist. The final action of the right side of the
above heuristic rule is to add the new task "⊗6Check examples of Sets⊗*" to the
agenda. When this gets selected, all the "slightly wrong" examples will be fixed
up. For example, {z,a,c,a,a} will be converted to {a,c,z}.
If any reliance is made on those unchecked examples, there is the danger of
incorrectly rejecting a valid conjecture. This is not too serious, since the
very first such reliance will boost the priority of the task
"⊗6Check examples of Sets⊗*", and it would then probably be the very next task
chosen.
. SSSEC(Intuitions)
.QQ
The mathematician does not work like a machine; we cannot overemphasize
the fundamental role played in his research by a special intuition
(frequently wrong), which is not common-sense, but rather a divination
of the regular behavior he expects of mathematical beings.
-- Bourbaki
.ESS
This facet turned out to be a "dud", and was later excised from all
the concepts. It will be described below anyway, for the benefit of
future researchers. Feel free to skip directly to the next
subsection.
The initial idea was to have a set of a few (3-10) large, global,
opaque LISP functions. Each of these functions would be termed an
"Intuition" and would have some suggestive name like "jigsaw-puzzle",
"see-saw", "archery", etc. Each function would somehow model the
particular activity implied by its name. There would be a multitude
of parameters which could be specified by the "caller" as if they
were the arguments of the function. The function would then work to
fill in values for any unspecified parameters. That's all the
function does. The caller would also have to specify which
parameters were to be considered as the "results" of the function.
For the see-saw, the caller might provide the weight of the
left-hand-side sitter, and the final position of the see-saw, and ask
for the weight of the right-hand sitter. The function would then
compute that weight (as any random number greater/less-than the
left-hand weight, depending on the desired tilt of the board). Or,
the caller might specify the two weights and ask for the final
position.
The See-saw function is an expert on this subject; it has
efficient code for computing any values which can be computed, and
for randomly instantiating any variables which may take on any value
(e.g., the first names of the people doing the sitting). When an individual
call is made on this function, the caller is not told how the final values
of the variables were computed, only what those values end up as.
So the Intuitions were to be experimental laboratories for AM,
wherein it could get some (simulated) real-world empirical data. If
the seesaw were the Intuition for ">", and weight corresponded to
Numbers, then several relationships might be visualized intuitively
(like the anti-symmetry of ">"). This is a nice idea, but in practice
the only relationships derived in this way were the ones that were
thought up while trying to encode the Intuition functions. This
shameful behavior led to the excision of the Intuitions facets
completely from the system.
As another example, suppose AM is considering composing two relations
R and S. If they have no common Intuition reference, then perhaps
they're not meaningfully composable. If they do both tie into the
same Intuition function, then perhaps that function can tell us
something about the composition. This is a nice idea, but in practice
very few prunings were accomplished this way, and no unanticipated
combinations were fused.
Each Intuition entry is like a "way in" to one of the few global
scenarios. It can be characterized as follows:
.BN
λλ One of the salient features of these entries -- and of the
scenarios -- is that AM is absolutely forbidden to look inside them,
to try to analyze them. They are ⊗4↓_opaque_↓⊗*. Most Intuition
functions use numbers and arithmetic, and it would be pointless to
say that AM discovered such concepts if it had access to those
algorithms all along.
λλ The second characteristic of an Intuition is that it be
⊗4↓_fallible_↓⊗*. As with human intuition, there is no guarantee
that what is suggested will be verified even empirically, let alone
formally. Not only does this make the programming of Intuition
functions easier, it was meant to provide a degree of "fairness" to
them. AM wasn't cheating quite as much if the See-saw function was
only antisymmetric 90% of the time.
λλ Nevertheless, the intuitions are very ⊗4↓_suggestive_↓⊗*. Many
conjectures can be proposed only via them. Some analogies (see the
next subsection) can also be suggested via common intuitions.
.E
After they were coded and running, I decided that the intuition
functions were unfair; they contained some major discoveries
"built-in" to them. They had the power to propose
otherwise-obscure new concepts and potential relationships.
They contributed nothing other than what was originally programmed into them;
⊗4they were not synergetic⊗*.
Due to this dubious character of
the contributions by AM's few Intuition functions,
they were removed from the system. All the examples and all the
discoveries listed in this document were made without their
assistance.
We shall now drop this de-implemented idea. I think there is some
real opportunity for research here.
For the benefit of any future researchers in this area,
let me point to the excellent
discussion of analogic representations in [Sloman 71].
. SSSEC(Analogies)
.QQ
The whole idea of analogy is that `Effects', viewed as a function of situation,
is a ↓_continuous_↓ function.
-- Poincare'
.ESS
As with Views and Intuitions, this facet is useful for shifting
between one part of the universe and another. Views dealt with
transformations between two specific concepts; Intuitions dealt with
transformations between a bunch of concepts and a large standard
scenario which was carefully hand-crafted in advance. In contrast,
this facet deals with transforming between a list of concepts and
another list of concepts.
Analogies operate on a much grander scale than Views. Rather than
simply transforming a few isolated items, they initiate the creation
of many new concepts. Unlike Intuitions, they are not limited in
scope beforehand, nor are they opaque. They are dynamically proposed.
The concept of "prime numbers" is ⊗4analogous⊗* to the notion of
"simple groups".
While not isomorphic, you might guess at a few relationships
involving simple groups just by my telling you this fact:
simple groups are to groups what primes are to numbers.$$
If a group is not simple, it can be factored.
Unfortunately, the factorization of a group into simple groups is not unique.
Another analogizing contact: For each prime p, we can
associate the cyclic group of order p, which is of course simple.
AM never came up with the concept of simple groups; this is just an illustration
for the reader. $
Let's take 3 elementary examples, involving very fundamental
concepts.
.XGENLINES←XGENLINES-1
.skip 1 BN PREFACE 1
λλ AM was told how to ↓_View_↓ a set as if it were a bag.
λλ AM was told it could ↓_Intuit_↓ the relation "⊗6≥⊗*" as the predetermined "See-saw"
function.
λλ AM, by itself, once ↓_Analogize_↓d that these two lists correspond:
.TABS 11, 24, 37 TURN ON "\" PREFACE 0
\<Bags\Same-length\Operations-on-and-into Bags>
\<Bags-of-T's\Equality\Those operations restricted to Bags-of-T's>
.E
.XGENLINES←XGENLINES-1
The concept of a bag, all of whose elements are "T"'s, is the unary
representation of ⊗4numbers⊗* discovered by AM. When the above
analogy (#3) is first proposed, there are many known Bag-operations$$
i.e., all entries on In-dom-of(Bag) and In-ran-of(Bag); a few of
these are: Bag-insert, Bag-union, Bag-intersection$, but there are as
yet no numeric operations$$ Examples of Operation whose domain/range
contains "Number". $. This triggers one of AM's heuristic rules, which
spurs AM on to finding the analogues of specific Bag-operations. That
is, what special properties do the bag-operations have when their
domains and/or ranges are restricted from Bags to Bags-of-T's (i.e,
Numbers). In this way, in fact, AM discovers Addition (by
restricting Bag-union to the Domain/range <Bags-of-T's Bags-of-T's →
Bags-of-T's>), plus many other nice arithmetic functions.
Well, if it leads to the discovery of Addition, that analogy is
certainly worth having. How would an analogy like that be proposed?
As the reader might expect by now, the mechanism
is simply some heuristic rule adding it as an entry to
the Analogies facet of a certain concept. For example:
.B816 INDENT 4,16,0
IF the current task has just created a canonical specialization C2 of
concept C1, with respect to operations F1 and F2, [i.e., two members
of C2 satisfy F1 iff they satisfy F2],
THEN add the following entry to the Analogies facet of C2:
.TABS 24,30,36 TURN ON "\"
\<C1\F1\Operations-on-and-into(C1)>
\<C2\F2\Those operations restricted to C2's>
.E
After generalizing "Equality" into the operation "Same-length", AM
seeks to find a canonical$$ A natural, standard form. All bags
differing in only "unimportant" ways should be transformed into the
same canonical form.
Two bags B1 and B2 which have the same length should get transformed into
the same canonical bag.
$ representation for Bags. That is, AM seeks a
canonizing function f, such that (for any two bags x,y)
.B816
⊗6Same-length(x,y) iff Equal( f(x), f(y) ).⊗*
.E
Then the range of f would delineate the set of "canonical" Bags. AM
finds such an f and such a set of canonical bags: the operation f
involves replacing each element of a bag by "T", and the canonical
bags are those whose elements are all T's. In this case, the above
rule triggers, with C1=Bags, C2=Bags-of-T's, F1=Same-length,
F2=Equality, and the analogy which is produced is the one shown as
example #3 above.
The Analogy facets are not implemented in full generality in the
existing LISP version of AM, and for that reason I shall refrain from
delving deeper into their format. Since good research has already
been done on reasoning by analogy$$ An excellent discussion of
reasoning by analogy is found in [Polya 54]. Some early work on emulating
this was reported in [Evans 68]; a more recent thesis on this topic is
[Kling 71]. $, I did not view it as a central feature of my work. Very
little space will be devoted to it in this document.
An important type of analogy which was untapped by AM was that
between heuristics. If two situations were similar, then conceivably the
heuristics useful in one situation might be useful (or have useful
analogues) in the new situation. Perhaps this is a viable way of
enlarging the known heuristics. Such "meta-level" activities were
kept to a minimum throughout AM, and this
proved to be a serious limitation.
Let me stress that the failure of the Intuitions facets to be
nontrivial was due to the lack of spontaneity which they possessed.
Analogies facets were useful and "fair" since their uses were not
predetermined by the author.
. SSSEC(Conjec's)
.if false then start;
of concept C is a list of
relationships which involve C.
We shall discuss its semantics (uses of this facet) before its syntax.
Perhaps the most obvious use for this facet would be to hold
conjectures which could not be phrased simply. Yet it turns out that
luckily (I think), all the conjectures "fell out" naturally as trivial
relationships,
e.g. simply as arcs in the Genl/Spec/Exs/Isas pointer format.
Specifically, the modal conjecture had the form "the range of F is not just
C, but actually S".
For example, AM restricted TIMES to perfect squares, and noted that the result
was not merely a number but a perfect square each time. The unique factorization
theorem was noticed similarly (the range of Prime-factorings was always a singleton,
not merely a set).
.ONCE TURN ON "{}"
In all the cases encountered by AM, there was never any real need for a place to
"park" an awkwardly-phrased conjecture, because ⊗4no awkward conjecture could ever
possibly be noticed⊗*. Why is this so?
AM was constructed explicitly on the assumption that
all (enough?) important theorems could be discovered in quite natural ways,
as very simple (already-known) relationships on already-defined concepts.
AM embodies several such assumptions about math research; they are collected and
packaged for display in Section
{[2]MODELSEC}.{[2]MODELSSEC}.{[2]MODELSSSEC}, on
page {[3]MODELPAGE}.
What else is this facet be useful for, if not the storage of awkwardly-worded
conjectures?
It is a good place to store ⊗4flimsy⊗* conjectures: those which were
strong enough to get considered, yet for which not much empirical confirmation
had been done.
This in fact was one important role of this facet.
For example, AM was initially told that there are two specializations of
Unordered-structures, namely Bags and Sets. But AM was not given any examples
of any structures at all. Early on, it chose the task "Fillin examples of Bags"
from the agenda. After filling them in, a heuristic rule had AM consider whether
or not this concept of Bags was really any more specialized than the concept
of Unordered-structures. To test this empirically, AM tried to verify whether or
not there were any examples of Unordered-structures that were ⊗4not⊗* examples
of Bags. Failure to find any led to proposing the conjecture "All Unordered-structures
are really Bags". This could have been recorded quite easily:
Bags was already known to be specialization of Unordered-structure, so all AM
had to do was tag it as a generalization as well (add "Bags" to the
Generalizations facet of the Unordered-structures concept). But a heuristic
rule which knows about such equivalence conjectures first asked whether
there were any specializations of Unordered-structures which had no known
examples, and for which AM had not (recently, at least) tried to fill in examples.
In fact, such an entry was "Sets". So the conjecture was stored on the Conjec
facet of Unordered-structures, and a new job was added to the agenda:
"Fill in examples of Sets". The reason was that such examples might
disprove this flimsy conjecture. In fact, the job already existed on the
agenda, so only the new reason was added, and its priority was boosted.
When such examples were found, they did of course disprove that conjecture:
each set was an Unordered-structure and yet was not a Bag.$$
Bags are not multisets, although those two notions are very closely
related to each other. Each set is a multiset by definition; but each set is
guaranteed by definition to ↓_not_↓ be a bag. $
This last example has suggested another use for this facet: holding
Another use for this facet is to hold
heuristic rules which are relevant to filling in and checking conjectures.
For example, the Conjec facet of Operations has some special heuristics which
look for certain kinds of relationships involving any given operation
(e.g., "Pick any example F(x)=y. See what interesting statements can be made
about y. Then try to verify or disprove each one by looking at the values of
all the other known calls on operation F"). The Conjec facet of Any-concept
will contain knowledge which is much more general in scope
(e.g., "See whether concept C is an example of some member of (C.Isa).Spec").
Compose.Conjec will contain more
specific heuristics (e.g.,
"See if the composition A-o-B is really no different from
B").
Given any concept C, AM will ripple upwards, locating Isas(C), and collect
the heuristics which are tacked onto their Conjec facets. These heuristic rules
will then be evaluated (in order of increasing generality), and some conjectures
will probably be proposed, checked, discarded, modified, etc.
In fact, each Conjec facet of each concept can have two separate subfacets:
Conjec.Fillin and Conjec.Check. The former contains heuristics for noticing
conjectures, the second for verifying and patching them up.
Conjec facets enable a kind of storage efficiency as well:
After discovering that all primes except 2 are Odd-primes, there is very
little reason to keep around Odd-primes as a separate concept from Primes.
Yet they are not quite equivalent. Primes.Conjec is a good place for AM to
store the conjecture "Prime(x) implies that x=2 or Odd(x)", and to
pull over to Primes any efficient definition/algorithm which
Odd-primes might possess
(patching it up to work for "2"), and then destroy the concept Odd-primes.
Another way out is merely to destroy "Primes", and make 2 a distinguished
number tacked onto the Just-barely-missed subfacet of
Odd-primes.Exs (just like "1" is already).
Here is another example: AM discovers that Set-insert-o-Set-insert is
the same as just Set-insert. That is, if you insert x twice into a set S, it's
no different than inserting it just once (because Sets don't allow multiple
copies of the same element). Then there's no longer any reason for keeping
Set-insert-o-Set-insert hanging around as a separate concept.
Instead, just add a small new entry to Set-insert.Conjec and forget that
space-consuming composition forever.
There is another use of the Conjec facet: untangling paradoxes.
It is with no sorrow that
I mention that this facility was never needed by AM: no genuine contradictions
ever were believed by AM. What would one look like? Suppose a chain of
Spec links indicates that X is a specialization of Y, and yet AM finds some
example x of X which does not satisfy Y.Definition).
So X is -- and is not -- a specialization of Y.
In such cases, the Conjecs facets of the concepts involved would indicate
which of those Spec links were initially-supplied (hence unchallengable),
which links were created based on formal verifications (barely challengable),
and which links were established based only on empirical evidence (yes, these
are the ones which would then fade into the sunset).
If it has to, AM should be able to recall the justification for each new link
it created. AM can deduce this by examining the Conjec facets of the concepts
involved.
Periodically (at huge intervals) AM chose a task of the form
"Check conjecs about C", at which time all the entries on
C.Conjec
would be re-examined
in light of existing data. Some would be discarded
(perhaps causing some Exs/Isa/Spec/Genl links to vanish with them). Some of the
conjectures might be believed much more strongly now (causing some new links
to be recorded). This turned out to be a surprisingly ineffective activity;
very few new revelations were obtained this way. Ultimately, this kind of task
was muzzled (AM was inhibited from doing this).
Theoretically, AM might possess rules which transformed a conjecture into a
more efficient algorithm for an operation, or which used the knowledge contained
therein to speed up an existing algorithm. Another sophisticated use of a conjec
would be to set up a new
representation scheme for a concept$$ e.g., after
unique factorization is discovered,
begin representing numbers as a bag of primes: n is represented as the prime
factorization of n. This is exponentially better than unary notation: bags-of-T's.
AM had a tiny ability for this kind of ongoing transformation, so crude it's
better left undescribed. $.
Finally, the Conjec's facet is used as a showcase,
to highlight some nice discovery that
AM wants to display. The user can look at the entries on each concept's Conjec
facet (after a long run) and get a better feeling for AM's abilities.
If there are several powerful conjectures listed for concept C,
then it appears to the
user that AM "understands" the concept much better than if C.Conjecs is empty.
Let's recapitulate the uses of this facet:
.BN SKIP 1
λλ Store awkwardly-phrased conjectures: this wasn't really useful.
λλ Store flimsy conjectures: apparent
relationships worth remembering, yet not quite believed.
λλ Hold
heuristics which notice and check conjectures.
λλ Obviate the need for many similar concepts:
Collapse the entire essence of a related concept into one or two relationships
involving this one.
λλ Untangling paradoxes: a historic record, which wasn't really used.
λλ Improve existing algorithms, definition testing procedures, representations.
λλ Display AM's most impressive observed relationships in a form which is easily
inspectable by the user.
.E
The syntax of this facet is simply a list of conjectures, where each conjecture
has the form of a relationship: (R a b c...d). R is the name of a known operation
(in which case, abc... are its arguments and we claim that d is its value),
or R is a predicate (and d is either True or False), or R is the name of a kind of
link (Genl, Spec, Isa, or Exs), and the claim is that a and b are related by R.
Here are three example of conjectures, illustrating the possible formats:
.BN SKIP 1
λλ ⊗6(Compose Set-insert Set-insert Set-insert)⊗1. This says that if you apply
the known operation Compose, to the two arguments Set-insert and Set-insert,
then the resultant composition is indistinguishable from Set-insert.
λλ ⊗6(Same-size Insert(S,S) S False)⊗1. That is, inserting a set into itself
will always (for finite sets) give you a set of a different length.
λλ ⊗6(Example-of Prime-factorings Function)⊗1.
This conjecture is the unique factorization
theorem. The operation which takes a number n, and finds all prime factorizations
of n, is claimed to be a function, not merely a relation.
That is, each n has precisely one such prime factoring.
.E
.end;
The "Conjec" facet of a concept C is a list of
relationships which involve C.
There are several uses for C.Conjec:
.BN SKIP 1
λλ Store awkwardly-phrased conjectures: this wasn't really useful,
since most conjectures fell out naturally as simple relationships,
expressable, e.g., as a single Genl arc, or a single Isa arc.
λλ Store flimsy conjectures: apparent
relationships worth remembering but not quite believed yet.
λλ Hold
heuristics which notice and check conjectures.
λλ Obviate the need for many nearly-indistinguishable concepts:
Collapse the entire essence of a concept like "Odd-primes"
into one or two relationships
involving "Primes"; then discard "Odd-primes".
λλ Untangling paradoxes: a historic record, to facilitate
backtracking in case of catastrophe, which (luckily!) wasn't ever needed.
λλ Improve existing algorithms (e.g., once you know primes are odd,
hunt only through odd numbers), improve
testing procedures, representations, etc.
λλ Display AM's most impressive observed relationships in a form which is easily
inspectable by the user.
.E
The syntax of this facet is simply a list of conjectures, where each conjecture
has the form of a relationship: (R a b c...d). R is the name of a known operation
(in which case, abc... are its arguments and we claim that d is its value).
For instance, "⊗6(Same-size Insert(S,S) S False)⊗1" is a conjecture
that
inserting a set into itself
will always give you a set of a different length.
This conjecture happens to be true for finite sets.
. SSSEC(Definitions)
A typical way to disambiguate a concept from all others is to provide
a "definition" for it.$$ As EPAM studies showed
[Feigenbaum 63],
one can
never be sure that this definition will specify the concept uniquely
for all time. In the distant future, some new concept may differ in
ways thought to be ignorable at the present time. $ Almost every
concept had some entries initially supplied on its "Definitions"
facet. The format of this facet is a list of entries, each one
describing a separate definition. A single entry will have the
following parts:
.BN
λλ Descriptors: Recursive/Linear/Iterative, Quick/Slow,
Opaque/Transparent, Once-only/Early/Late, Destructive/Nondestructive.
λλ Relators: Reducing to the definition of concept X, Same as Y
except..., Specialized version of Z, Using the definition of W, etc.
λλ Predicate: A small, executable piece of LISP code, to tell if any
given item is an example of this concept.
.E
.if false then start;
The predicate or "code" part of the entry must be faithfully described by the
Descriptors, must be related to other concepts just as the Relators
claim.
The predicate must be a LISP function which
take argument(s) and return either T or NIL (for
True/False), depending on whether or not the argument(s) can be
regarded as examples of the concept.
The argument "α{A Bα}" should
satisfy the predicate of any valid definition entry of the Sets
concept. This triple of arguments <{A B}, {A C}, {A B C}> should
satisfy any definition of the Set-union concept, since the third is
equal to the Set-union of the first two arguments.
.end;
.XGENLINES←XGENLINES-1;
Here is a typical entry from the Definitions facet of the Set-union concept:
.WBOX(11,11)
MBOX $
MBOX Descriptors: Slow, Recursive, Transparent $
MBOX $
MBOX Relators: Uses the algorithm for Set-insert, Uses the definition of Empty-set, $
MBOX Uses the definition of Set-equal, Uses the algorithm for Some-member, $
MBOX Uses the algorithm for Set-delete, Uses the definition of Set-union $
MBOX $
MBOX Code: λ (A B C) $
MBOX IF Empty-set.Defn(A) THEN Set-equal.Defn(B,C) ELSE $
MBOX X ← Some-member.Alg(A) $
MBOX A ← Set-delete.Alg(X,A) $
MBOX B ← Set-insert.Alg(X,B) $
MBOX Set-union.Defn(A,B,C) $
.SUPAGE: PAGE;
.EBOX
Let me stress that this is just one entry from one facet of one
concept.
.if false then start;
The notation "X ← Some-member.Alg(A)" means that any one algorithm
for the concept Some-member should be accessed, and then it should be
run on the argument A. The result, which will be an element of A, is
to be assigned the name "X". The effect is to bind the variable X to
some member of set A.
In the actual LISP implementation, the
ELSE part of the conditional is really coded$$
The expression "(f.Defn a1 a2...)" means "apply the predicate part of
a definition of f, to arguments a1, a2,...". This definition is to be
randomly selected from the entries on the Definitions facet of
concept f. $ as:
.B0
(Set-union.Defn (Set-delete.Alg (SETQ X (Some-member.Alg A)) A)
(Set-insert.Alg X B)
C
)
.E
.end;
This particular definition is not very efficient, but it is described
as Transparent. That means it is very well suited to analysis and
modification by AM itself. Suppose some heuristic rule wants to
generalize this definition. It can peer inside it, and, e.g., replace
the base step call on Set-equal, by a call on a generalization of
Set-equal (say "Same-length"$$ For disjoint sets, the new definition
would specify the operation which we call "addition". $).
How could ⊗4different⊗* definitions help here? Suppose there were a
definition which first checked to see if the three arguments were
Set-equal to each other, and if so then it instantly returned T as
the value of the definition predicate; otherwise, it recurred into
Set-union.Defn again. This might be a good algorithm to try at the
very beginning, but if the Equality test fails, we don't want to keep
recurring into this definition. This algorithm should thus have a
descriptor labelling it ONCE-ONLY EARLY.
.if false then start;
A typical kind of entry for the Definitions facet of an operation is
to simply call on the ⊗4Algorithms⊗* part of that same concept. Here
is such an entry from the Definitions facet of the Set-union concept:
.WBOX(12,14)
MBOX Descriptors: none $
MBOX $
MBOX Relators: Uses the definition of Set-equal, Uses the algorithm for Set-union $
MBOX $
MBOX Code: λ (A B C) Set-equal.Defn(C, Set-union.Alg(A,B)) $
.EBOX
This definition is a trivial call on the "Algorithms" facet of
Set-union. That is, one way to test whether C is the set-union of A
and B, is simply to ⊗4run⊗* set-union on A and B, and compare the
result against C. The descriptors and relators of the particular
algorithm which is chosen will then be added to the descriptors and
relators which exist so far on this entry. Note that the box above
(like the box on the previous page) is simply one entry on the
Definitions facet of the Set-union concept.
.end;
There are three purposes to having descriptors and relators hanging
around:
.BN
λλ For the benefit of the user. AM appears more intelligent because
it can ⊗4describe⊗* the kind of definition it is using -- and why.
λλ For the sake of efficiency. When all AM wants to do is to evaluate
Set-union(A,B), it's best just to grab a ⊗4fast⊗* definition. When trying to
generalize Set-union, it's more appropriate to
modify a very clean, transparent definition -- even if it is a slow one.
λλ For the benefit of the heuristic rules. Often, a left- or a
right-hand-side will ask about a certain kind of definition. For
example, ⊗6"If a transparent definition of X exists, then try to
specialize X"⊗*.
.E
.if false then start;
Granted that Descriptors and Relators are useful, how do these
"meta-level" modifiers get filled in, for newly-created$$ For
initially-supplied definition entries, the author hand-coded these
modifiers. $ concepts? All such powers are embedded in the fine
structure of the heuristic rules. This is true for the Algorithms
facet as well, and will be illustrated in the very next subsection.
Let me pull back the curtain a little further, and expose the actual
implementation of these ideas in AM. The secrets about to be
revealed will not be acknowledged anywhere else in this document.
They may, however, be of interest to future researchers. Each
concept may have a cluster of Definition facets, just as it can have
several kinds of Examples facets. These include three types:
Necessary and sufficient definitions, necessary definitions, and
sufficient definitions. These three types have the usual
mathematical meanings. All that has been alluded to before (and
after this subsection) is the necc&suff type of definition (x is an
example of C ⊗4if and only if⊗* x satisfies C.Def/necc&suff). Often,
however, there will be a much quicker sufficient definition (x
satisfies C.Def/suf, ⊗4only if⊗* x is certainly a C). Similarly,
entries on C.Def/nec are useful for quickly checking that x is
⊗4not⊗* an example of C (to check this, it suffices to verify that x
⊗4fails⊗* to satisfy a necessary definition of C).
So given the task of deciding whether or not x is an example of C, we
have many alternatives:
.BN
λλ If x is a concept, see if C is a member of x.ISA (if so, then x is
an example of C).
λλ Try to locate x within C.Exs. (depending upon the flavor of subfacet
on which x is found, this may show that x is or is not
an example of C).
λλ If x is a concept, ripple to collect ISA's(x), and see if C is a
member of ISA's(x).
λλ If there is a fast sufficent definition of C, see if x satisfies
it.
λλ If there is a fast necessary definition of C, see if x fails it
(if so, then x is ⊗4not⊗* an example of C).
λλ If there is a necessary and sufficient definition of C, see whether
or not x satisfies that definition (this may show that x is or is not
an example of C).
λλ Try to locate x within C.Exs. (depending upon the flavor of subfacet
on which x is found, this may show that x is or is not
an example of C).
λλ Recur: check to see if x is an example of any specialization of
C.
λλ Recur: check to see if x is ⊗4not⊗* an example of some
generalization of C (if so, then x is ⊗4not⊗* an example of C),
.E
In fact, there is a LISP function, IS-EXAMPLE, which performs those
steps in that order. At each moment, there is a timer set, so even
if there is a necessary and sufficient definition hanging around, it
might run out of time before settling the issue one way or the other.
Each time the function recurs, the timer is granted a smaller and
smaller quantum, until finally it has too little to bother recurring
anymore. There is a potential overlap of activity: to see if x is an
example of C, the function might ask whether x is or is not an
example of a particular generalization of C (step 9, above); to test
⊗4that⊗*, AM might get to step 8, and again ask if x is an example of
C. Even though the timer would eventually terminate this fiasco (and
even though the true answer might be found despite this wasted
effort) it is not overly smart of AM to fall into this loop.
Thdβefore, a stack is maintained, of all concepts whose definitions the
IS-EXAMPLE function tried to test on argument x. As the function
recurs, it adds the current value of C to that stack; this value
gets removed when the recursion pops back to this level, when that recursive call
"returns" a value.
.end;
. SSSEC(Algorithms)
Earlier, we said that each concept can have any facets from the universal fixed set
of 25 facets.
This is not strictly true. Sometimes, a whole class
of concepts will possess a certain type of facet which no others may meaningfully
have.
.if false then start;
If C can have that facet, then so can any specialization of C.
Typically, there will be some concept C such that the examples of C are precisely the
set of concepts which can possess the new facet.
.end;
That is, there will be a ⊗4domain of applicability⊗* for the facet, just
as we defined such domains of applicability for heuristics.
For example, consider the "Domain/Range" facet. It is meaningful only to
"operations".
Let's view this in a more general light.
For each facet f, the only concepts which
can have entries for facet f are examples of some particular concept D(f)
-- the "J" stands for "jargon".
D(f) is the domain of applicability of facet f.
If C is any concept which is not an example of D(f), then it can never
meaningfully possess any entries for that facet f.
For almost all facets f, D(f) is "Any-concept". Thus any concept can possess
almost any facet.
For example, D(Defn)="Any-concept", so any concept may have definitions.
But D(Domain/range)="Operation". So only operations can have domain/range facets.
Similarly, D(Algorithms)="Actives". This facet is the subject of this section.
The Algorithms facet is present for all -- but only
for -- Actives
(predicates, relations, operations).
The representation is, as usual, a list of entries, each one
describing a separate algorithm, and each one having three parts:
Descriptors, Relators, Program.
.if false then start;
.BN TURN OFF "-"
λλ Descriptors: Recursive/Linear/Iterative, Quick/Slow, Opaque/Transparent,
Once-only/Early/Late,
Destructive/Nondestructive.
λλ Relators: Reducing to the algorithm for concept X,
Same as Y except...,
Specialized version of Z's algorithm, Using the algorithm for W, etc.
λλ Program: A small, executable piece of LISP code, for actually running C.
.E
.end;
.RECURPAGE: PAGE;
Note the similarity to the format for the Definitions facets of concepts.
Instead of a LISP predicate, however, the Algorithms facets possess a LISP function
(an executable piece of code whose value
will in general be other than True/False).
.if false then start;
That "program" part of the entry must be
faithfully described
by the Descriptors, must be related to other concepts just as the
Relators claim, must take
arguments and return values as specified in the Domain/Range facet of C, and
when run on any arguments, the resultant
<args value> pair must satisfy the Definitions facet of C.
There is an extra level of sophistication which is available but rarely used in AM.
The descriptors can themselves be small numeric-valued functions. For example,
instead of just including the Descriptor "Quick",
and instead of just giving a fixed number for the speed of the algorithm,
there might be a little program there, which looked at the arguments fed to the
algorithm, and then estimated how fast this algorithm would be.
The main reason for not using this feature more heavily is that most of the
algorithms are fairly fast, and fairly constant in performance. It would be silly to spend
much time recomputing their efficiency each time they were called. If the
algorithm is recursive, this conjures up even sillier pictures.
The main reason in support of using this feature is of course "intelligence":
in the long run, processing a little bit before deciding which algorithm to run
⊗4has⊗* to be the winning solution. At the moment, it is not yet cost-effective.
Here is a typical entry from the Algorithms$$
note that it is similar to -- but not identical to -- the entry shown
on page {[3]SUPAGE}, of a ↓_Definition_↓ of Set-union. $
facet of the Set-union concept:
.WBOX(11,11)
MBOX $
MBOX Descriptors: Slow, Recursive, Transparent $
MBOX $
MBOX Relators: Uses the algorithm for Set-insert, Uses the definition of Empty-set, $
MBOX Uses the algorithm for Some-member, Uses the algorithm for Set-insert, $
MBOX Uses the algorithm for Set-union $
MBOX $
MBOX Code: λ (A B) $
MBOX IF Empty-set.Defn(A) THEN B ELSE $
MBOX X ← Some-member.Alg(A) $
MBOX A ← Set-delete.Alg(X,A) $
MBOX B ← Set-insert.Alg(X,B) $
MBOX Set-union.Alg(A,B) $
.EBOX
Note that the Descriptors don't say whether this algorithm is destructive$$
A LISP algorithm is destructive if it physically, permanently modifies the
list structures it is fed as arguments. Set-union(A,B) is destructive if
-- after running -- A and B don't have the same values they started with.
The advantages of destructive operations are increased speed,
decreased space used up,
fewer
assignment statements. The danger of course is in accidentally destroying some
information you didn't mean to. $
or not.
That means that this same algorithm can be used either destructively or not,
depending on what AM wants.
More precisely, it's up to the algorithms which get called on by this one.
If they are all
chosen to be destructive, so will Set-union. If they all copy their arguments first
then Set-union will ⊗4not⊗* be destructive.
For example, note how the algorithm calls on Set-insert(X,B). If this is destructive,
then at the end B will have been physically modified to contain X; the original
contents of B will be lost.
This particular algorithm is not very efficient, but it is described as Transparent.
That means it is very well suited to analysis and modification by AM itself.
Suppose
some heuristic rule
wants to specialize this algorithm. It can peer inside it, and,
e.g., replace the variable X in (Set-insert X B) by the constant "T".$$
This is a fairly useless new operation, of course. It adds T to B unless A is empty,
in which case this operation has no effect at all. $
Why should AM bother storing multiple algorithms for the same concept?
Consider this example again, of Set-union. Suppose there were an algorithm
which first checked to see if the two arguments were Equal to each other, and if so
then it instantly returned one of them as the final value for Set-union;
otherwise, it recurred into Set-union.Alg.
This might be a good algorithm to try
at the very beginning, but if the Equality test fails, we
don't want to keep recurring into this definition.
This algorithm should thus have a descriptor labelling it ONCE-ONLY EARLY.
Also, there is an iterative algorithm which checks to see if A
equals B,
and if so then it returns B. If not, the algorithm proceeds to check that A
is shorter than B,
and if not it switches them. Finally, it enters an iterative loop similar to the
recursive one above: it repeatedly transfers an element from A to B, using
Some-member, Set-delete and Set-insert. This iterative loop repeats until
A becomes empty.
While more efficient than the recursive one, this definition is less transparent.
An even more efficient algorithm is provided, but it is totally opaque:
.WBOX(18,18)
MBOX Descriptors: Quick, Non-recursive, Non-destructive, Opaque $
MBOX $
MBOX Relators: none $
MBOX $
MBOX Code: λ (A B) (UNION A B) $
.EBOX
This algorithm calls on the LISP function "UNION" to perform the set-union.
It is the "best" algorithm to choose unless space is critical, in which case a
destructive algorithm must be chosen, or unless AM wishes to inspect it rather
than run it, in which case a transparent one must be picked.
.end;
All the details about understanding the descriptors and relators are embedded in the
fine structure of the heuristic rules. A left-hand-side may test whether a
certain kind of algorithm exists for a given concept. A right-hand-side which
fills in a new algorithm must also worry about filling
in the appropriate descriptors
and relators. As with newly created concepts, such information is trivial to fill in
at the time of creation, but becomes much harder after the fact.
Here is a typical heuristic rule which results in a new entry being added to the
Algorithms facet of the newly-created concept named Compose-Set-Intersect&Set-Intersect:
.B816
.ONCE INDENT 4
IF the task is to Fillin Algorithms for F,
and F is an example of Composition
and F has a definition of the form F≡GoH,
and F has no transparent, nonrecursive algorithm,
.ONCE INDENT 4
THEN add a new entry to the Algorithms facet of F,
with Descriptors: Transparent, Non-recursive
with Relators: Reducing to G.Alg and H.Alg,
Using the Definition of <G.Domain>
with Program: λ (||<G.Domain>||,||<H.Domain>||-1,X)
.INDENT 30
(SETQ X (H.Alg ||<G.Domain>||))
(AND
.INDENT 33
(<G.Domain>.Defn X)
(G.Alg X ||<H.Domain>||-1))
.E
The intent of the little program which gets created
is to apply the first operator, check that the
result is in the domain of the second, and then apply the second operator.
The expression ||<G.Domain>|| means find a domain/range entry for G,
count how many domain components there are, and form a list that long
from randomly-chosen variable names (u,v,w,x,y,z).
For the case mentioned above, F = Compose-Set-Intersect&Set-Intersect,
G = Set-Intersect,
and H = Set-Intersect. The domain of
G is a pair of Sets, so
||<G.Domain>|| is a list
of 2 variables, say (u v). Similarly,
||<H.Domain>||-1 is a list
of 1 variable, say (w). Putting all this together, we see that
the new definition entry created for
Compose-Set-Intersect&Set-Intersect
would look like this:
.WBOX(15,15)
MBOX $
MBOX Descriptors: Non-Recursive, Transparent $
MBOX $
MBOX Relators: Reducing to Set-Intersect.Alg, Using the definition of Sets $
MBOX $
MBOX Code: λ (u,v,w,X) $
MBOX (SETQ X (Set-Intersect.Alg u v)) $
MBOX (AND $
MBOX (Sets.Defn X) $
MBOX (Set-Intersect.Alg X w) $
.EBOX
.if false then start;
Let me make clear here one "kluge" of the AM program.
.end;
At times, AM will
be capable of producing only a slow algorithm for some new concept C.
.if false then start;
For example, TIMES-1-(x) was originally defined by AM as a blind, exhaustive search
for bags of numbers whose product is x. As AM uses that algorithm more and more,
AM records how slow it is. Eventually, a task is selected of the form
⊗6"Fillin new algorithms for C"⊗*, with the two reasons being that the existing
algorithms are all too slow, and they are used frequently.
At this point, AM should draw on a body of rules which take a declarative
definition and transform it into an efficient algorithm, or which take an
inefficient algorithm and speed it up. Doing a good job on just those rules
would be a mammoth undertaking, and the author decided to omit them.
Instead, the system will occasionally beg the user for a better (albeit
opaque) algorithm for some particular operation.
In general, the only requests were for inverse operations, and even then only
a few of them.
.end;
The reader who wishes to know more about rules for creating
and improving LISP algorithms is directed to [Darlington and Burstall 73].
A more general discussion of the principles involved can be found in [Simon 72].
. SSSEC(Domain/Range)
Another facet possessed only by active concepts is Domain/Range.
The syntax of this facet is quite simple. It is a list of entries, each of the form
⊗6< D↓1 D↓2... α→ R >⊗*, where there can be any number of D↓i's preceding the arrow,
and R and all the D↓i's are the names of concepts.
Semantically, this entry means that the active concept may be run on
a list of arguments
where the first one is an example of D↓1, the second an example of D↓2, etc.,
and in that case will return a value
guaranteed to be an example of R.
In other words, the concept may be considered a relation on the
Cartesian product
D↓1xD↓2x...xR.
We shall say that the ⊗4domain⊗* of the concept is
D↓1xD↓2x..., and that its ⊗4range⊗* is R. Each D↓i is called a
⊗4component⊗* of the domain.
For example, here is what the Domain/Range facet of TIMES might look like:
.WBOX(17,24)
MBOX α{ $
MBOX < Numbers Numbers α→ Numbers > $
MBOX < Odd-numbers Odd-numbers α→ Odd-numbers > $
MBOX < Even-Numbers Even-Numbers α→ Even-numbers > $
MBOX < Odd-numbers Even-Numbers α→ Even-Numbers > $
MBOX < Perf-Squares Perf-Squares α→ Perf-Squares > $
MBOX < Bags-of-Numbers α→ Numbers > $
MBOX α} $
.EBOX
.if false then start;
Here is what the Domain/Range facet of Set-Union might look like:
.WBOX(20,27)
MBOX α{ $
MBOX < Sets Sets α→ Sets > $
MBOX < Nonempty-sets Sets α→ Non-empty-sets > $
MBOX < Sets-of-Sets α→ Sets > $
MBOX α} $
.EBOX
.end;
The Domain/Range part is useful for pruning away absurd compositions, and
for syntactically suggesting compositions and "coalescings".
Let's see what this means.
Suppose some rule sometime tried to compose TIMES⊗7o⊗*Set-union.
A rule tacked onto Compose says to ensure that the range of Set-union
at least intersects
(and preferably is ⊗4equal⊗* to)
some component of the domain of TIMES. But there
are no entities which are both sets and numbers;
.if false then start;
$$ Why? The number n, to AM, is represented in unary, as a bag of n T's.
None of these are sets.
The composition "TIMESoBAG-UNION" would have made sense to AM, but would have
been defined only for bags-of-T's. Then TIMESoBAG-UNION(x,y,z) would be just
x(y+z).
$
.end;
ergo this fails
almost instantaneously.
.if false then start;
This is too bad, since there was probably a good reason (e.g., intuition)
for trying this composition. If the activation energy
(priority of the current task)
is high enough, AM
will continue trying to force it through.
The failure arose because Sets could not be viewed as if they were Numbers.
A relevant rule says:
.B816
IF you want to view X's as if they were Y's,
THEN seek an interesting operation F from X to Y, to do the viewing.
.E
So AM had to locate any and all operations whose domain/range had an
entry of the form <Setsα→Numbers>.
The only such operation known to AM at the time was F=Length.
So the composition produced was TIMES[X, Length(Set-union(Y,Z))].
Notice that if the composition Set-union⊗7o⊗*Set-union is proposed, there will be
no conflict, since the range of Set-union obviously intersects one component
of the domain of Set-union.
How can AM determine the domain/range of this composition? A rule tacked onto
Compose indicates that if F=G-o-H, and a domain/range entry for G is
<A...X...B α→ C>, and an entry for H is <D...E α→ Y>, and Y intersects X, then
an entry for F's domain/range is <A...D...E...B α→ C>. That is, the domain
of H is substituted for the single component of the domain of G which can be
shown to intersect the range of H.
Purely syntactically, AM can thus compute some domain/range entries for the
composition Set-union-o-Set-union.
.BEGIN FILL SELECT 6 PREFACE 0 INDENT 4,8,0; TURN OFF "-";
< Sets Sets α→ Sets> and < Sets Sets α→ Sets> combine to yield
< Sets Sets Sets α→ Sets >;
<Non-empty-sets Sets α→ Non-empty-sets> and <Sets Sets α→ Sets> combine to yield
<Non-empty-sets Sets Sets α→ Non-empty-sets>;
.E ONCE PREFACE 0
and so on. Similarly, one can compute an entry for the domain/range facet of the
previous composition of three operations TIMES-o-Length-o-Set-union:
.BEGIN FILL SELECT 6 PREFACE 0 INDENT 4,8,0
< Sets Sets α→ Sets>, < Sets α→ Numbers>, and < Numbers Numbers α→ Numbers >
combine to yield
< Numbers Sets Sets α→ Numbers >
.E
So when computing TIMES( X, Length( Set-union(Y,Z))), both Y and Z can be
sets, and X a number, and the result will be a number.
.end;
The claim was also made that Domain/Range facets help propose plausible coalescings.
By "⊗4coalescing⊗*" an operation,
we mean defining a new one, which differs from the original one in that
a couple of the arguments must now coincide. For example,
coalescing TIMES(x,y) results in the new operation F(x) defined as TIMES(x,x).
Syntactically, we can coalesce a pair of domain components of the domain/range
facet of an operation if those two domain components are equal, or if
one of them is a specialization of the other, or even if they merely intersect.
In the case of one related to the other by specialization, the more specialized
concept will replace both of them, In case of merely intersecting, an extra test
will have to be inserted into the definition of the new coalesced operation.
Given this domain/range entry for Set-insert: < Anything Sets α→ Sets >, we see that
it is ripe for coalescing. Since Sets is a specialization of Anything, the new
operation F(x), which is defined as Set-insert(x,x), will have a domain/range
entry of the form < Sets α→ Sets >. That is, the specialized concept Sets
will replace both of the old domain elements (Anything and Sets).
F(x) takes a set x and inserts it into itself. Thus F({a,b})={a,b,{a,b}}.
In fact, this new operation F is very exciting because it always seems to give
a new, larger set than the one you feed in as the argument.
We have seen how the Domain/range facets can
prune away meaningless coalescings, as well as meaningless
compositions. Any proposed composition or coalescing will at least be syntactically
meaningful. If all compositions are proposed only for at least one good
semantic reason, then those passing the domain/range test, and hence
those which ultimately get created, will all be valuable new concepts.
Since almost all coalescings are semantically interesting, ⊗4any⊗* of them which
have a valid Domain/Range entry will get created and probably will be interesting.
This facet is occasionally used to suggest conjectures to investigate. For example,
a heuristic rule says that if the domain/range entries have the form
<D D D... → genl(D) >, then it's worthwhile seeing whether the value of this
operation doesn't really always lie inside D itself. This is used right after the
Bags↔Numbers analogy is found, in the following way. One of the Bag-operations
known already is Bag-union. The analogy causes AM to consider a new operation,
with the same algorithm as Bag-union, but restricted to Bags-of-T's
(numbers in unary
representation). The Domain/range facet
of this new, restricted mutation of Bag-union
contains only this entry:
<Bags-of-T's Bags-of-T's → Bags>. Since Bags is a generalization of Bags-of-T's, the
heuristic mentioned above triggers,
and AM sees whether or not the union of two Bags-of-T's is
always a bag containing only T's. It appears to be so, even in extreme cases, so the
old Domain/range entry is replaced by this new one:
<Bags-of-T's Bags-of-T's → Bags-of-T's>.
When the user asks AM to call these bags-of-T's "numbers", this entry becomes
<Numbers Numbers → Numbers>.
In modern terms, then, the conjecture suggested was that the sum of two numbers
is always a number.
To sum up this last ability in fancy language,
we might say that
one mechanism for proposing
conjectures is the prejudicial belief in the unlikelihood of asymmetry.
In this case, it is asymmetry in the parts of a Domain/range entry that
draws attention.
Such conjecturing can be done by any action part of any heuristic rule;
the Conjec facet entries don't have a monopoly on initiating this type of activity.
. SSSEC(Worth)
How can we represent the worth of each concept? Here are some
possible suggestions:
.BN
λλ The most intelligent
(but most difficult)
solution is "purely symbolically". That is,
an individualized description of the good and bad points of the
concept; when it is useful, when misleading, etc.
λλ A simpler solution would be to "standardize" the above symbolic
description once and for all, fixing a universal list of questions.
So each concept would have to answer the questions on this list (How
good are you at motivating new concepts?, How costly is your
definition to execute?,...). The answers might each be symbolic;
e.g., arbitrary English phrases.
λλ To simplify this scheme even more, we can assume that the answers
to each question will be numeric-valued functions (i.e, LISP code
which can be evaluated to yield a number between 0 and 1000). The
vector of numbers produced by ↓_Eval_↓uating all these functions will
then be easy to manipulate (e.g. using dot-product, vector-product,
vector-addition, etc.), and the functions themselves may be inspected
for semantic content. Nevertheless, much content is lost in passing
from symbolic phrases to small LISP functions.
λλ A slight simplification of the above would be to just store the
vector of numbers answering the fixed set of questions; i.e., don't
bother storing a bunch of programs which compute them dynamically.
λλ Even simpler would be to try to assign a single "worthwhileness"
number to each concept, in lieu of the vector of numbers. Simple
arithmetic operations could manipulate Worth values then. In some
cases, this linear ordering seems reasonable ("primes" really are
better than "palindromes".) Yet in many cases we find concepts which
are too different to be so easily compared (e.g., "numbers" and
"angles".)
λλ The least intelligent solution is none at all: each concept is
considered equally worthwhile as any other concept. This threatens
to be combinatorial dynamite.
.E
As we progress along the intelligent→→→trivial dimension, we find
that the schemes get easier and easier to code, the Worth values get
easier and easier to deal with, but the amount of reliable knowledge
packed into them decreases.
Initially, scheme ⊗6#3⊗* above was chosen for AM: a vector of numeric-valued
procedural
answers to a fixed set of questions. Here are those questions, the
components of the Worth vectors for each concept:
.BN
λλ Overall aesthetic worth.
λλ Overall utility. Combination of usefulness, ubiquity.
λλ Age. How many cycles since this concept was created?
λλ Life-span. Can this concept be forgotten yet?
λλ Cost. How much cpu time has been spent on this concept, since its
creation?
.E
Notice that in general no constant number can answer one of these
questions once and for all (consider, e.g., Life-span). Each `answer'
had to be a numeric-valued LISP function.
A few questions which crop up often are not present on this list,
since they can be answered trivially using standard LISP functions
(e.g., "How much space does concept C use up?" can be found by
calling the function "COUNT" on the property-list of the LISP atom
"C").
Another kind of question, which was anticipated and did in fact come
up frequently, is of the form "How good are the entries on facet F of
this concept?", for various values of F. Since there are a couple
dozen kinds of facets, this would mean adding a couple dozen more
questions to the list. The line must be drawn somewhere. If too much
of AM's time is drained by evaluating where it is already, it can
never progress.
The heuristic rules are responsible for initially setting up the
various entries on the Worth facets of new concepts, and for
periodically altering those entries for ⊗4all⊗* concepts, and for
delving into those entries when required.
.ONCE TURN ON "{}"
Recent experiments have shown (see Experiment 1, page {[3] EX3PAGE})
there was little change in behavior when each vector of functions was
replaced by a single numeric function (actually, the sum of the
values of the components of the "old" vector of functions). There
wasn't even too much change when this was replaced by a single
number. There ⊗4was⊗* a noticeable degradation (but no collapse) when
all the concepts' numbers were set equal to each other initially.
For the purposes of this document, then (except for this page and the
discussion of Experiment 1), we may as well assume that each concept
has a single number (between 0 and 1000) attached as its overall
"Worth" rating. This number is set$$ The author initially sets this
value for the 115 initial concepts. Heuristic rules set it for each
concept created by AM. $ and referenced and updated by heuristic
rules. Experiment 1 can be considered as showing that a more
sophisticated Worth scheme is not necessary for the particular kinds
of behaviors that AM exhibits.
. SSSEC(Interest)
Now that we know how how to judge the overall worth of the concept
"Composition", let's turn to the question of how interesting some
specific composition is. Unfortunately, the Worth facet really has
nothing to say about that problem. The Worth of the concept "Compose"
has little effect on how interesting a particular composition is:
"Count-o-Divisors-of" is very interesting, and "Insert-o-Member"$$
INSERToMEMBER(x,y,z)α≡ if xεy, then insert `T' into z, else insert
`NIL' into z. $ is less so. The Worth facets of ⊗4those⊗* concepts
will say something about their overall value. And yet there is some
knowledge, some "features" which would make any composition which
possessed them more interesting than a composition which lacked them:
.BN
Are the domain and range of the composition equal to each other?
Are interesting properties of each component of the composition
preserved?
Are undesirable properties lost (i.e., ⊗4not⊗* true about the
composition)?
Is the new composition equivalent to some already-known operation?
.E
These hints about "features to look for" belong tacked onto the
Composition concept, since they modify all compositions. Where and
how can this be done?
For this purpose each concept -- including "Composition" -- can have
entries on its "⊗4Interest⊗*" facet. It contains a bunch of features
which (if true) would make any particular example of the current
concept interesting.
The format for the Interest facet is as follows:
.BEGIN group; NOFILL INDENT 4 PREFACE 0 SELECT 6
< Conflict-matrix
<Feature⊗B1⊗*, Value⊗B1⊗*, Reason⊗B1⊗*, Used⊗B1⊗*>
<Feature⊗B2⊗*, Value⊗B2⊗*, Reason⊗B2⊗*, Used⊗B2⊗*>
⊗8###⊗*
<Feature⊗BK⊗*, Value⊗BK⊗*, Reason⊗BK⊗*, Used⊗BK⊗*>
.ONCE INDENT 39
>
.apart; E
This is the format of the facet itself, not of each entry. The
conflict-matrix is special and will be discussed below. Each
Feature/Value/Reason/Used quadruple will be termed an "entry" on the
Interest facet.
Each "Feature⊗Bi⊗*" is a LISP predicate, indicating whether or not
some interesting property is satisfied. The corresponding
"Value⊗Bi⊗*" is a numeric function for computing just how valuable
this feature is. The "Reason⊗Bi⊗*" is a token (usually an English
phrase) which is tacked along and moved around, and can be inspected
by the user. The "Used⊗Bi⊗1" subpart is a list of all the concepts
whose definitions are known to incorporate$$ Not ↓_SATISFY_↓ the
feature. Thus the general concept Domain=Range-op ↓_incorporates_↓
the feature "range(x)is one component of domain(x)" as just one of
the conjuncts in its definition. On the other hand, Set-union
↓_satisfies_↓ the feature, since its range, Sets, really is one
component of its domain. $ this feature; all examples of such
concepts will then automatically satisfy this Feature⊗Bi⊗*.
.GROUP
For example, here is one entry from the Interest facet of Compose:
.B816
FEATURE: Domain(Arg1)=Range(Arg2)
VALUE: .4 + .4xWorth(Domain(Arg1)) + .2xPriority(current task)
REASON: "The composition of Arg1 and Arg2 will map from C back
into C"
USED: Compose-with-self-Domain=Range-operation, Interesting-compose-4
.E
.APART
Just as with Isa's and Generalizations, we can make a general
statement about Interest features:
.ONCE PREFACE 1 INDENT 6
⊗6Any feature tacked onto the Interest facet of any member of
ISA's(C), also applies to C.⊗*
.ONCE PREFACE 1
That is, X.Interest is relevant to C iff C is an example of X. For
example, any feature which makes an operation interesting, also makes
a composition interesting.
So we'd like to define the function Interests(C) as the union of the
Interest features found tacked onto any member of ISA's(C).$$ Recall
that the formula for this is ISA's(C) =
Generalizations(Isa(Generalizations(C))). $ But some of these might
have already been conjoined to a definition, to form the concept C
(or a generalization of C). So all C's will trivially (by
definition) satisfy such features. The USED subparts can be employed
to find such features. In fact, the final value of Interests(C) is
the one computed above, using ISA's(C), but after eliminating all the
features whose USED subparts pointed to any member of ISA's(C).
This covers the purpose of each subpart of each entry on a typical
Interest facet. Now we're ready to motivate the presence of the
Conflict-matrices.
Often, AM will specialize a concept by conjoining onto its definition
some features which would make any example of the concept
interesting. So ⊗4any⊗* example of this new specialized concept is
thus guaranteed to be an ⊗4interesting⊗* example of the old concept.
Sometimes, however, a pair of features are exclusive: both of them
can never be satisfied simultaneously. For example, a composition can
also be interesting if "arg2" is an operation from Range(arg1) into a
set which is much more interesting than either Domain(arg1) or
Range(arg1). Clearly, this feature and the one shown above can't
both be true ("x=y" and "x much more interesting than y" can't occur
simultaneously). If AM didn't have some systematic way to realize
this, however, it might create a new concept, called
Interesting-composition, defined as any composition satisfying both
of those features. But then this concept will be vacuous: ⊗4no⊗*
operation can possibly satisfy that over-constrained definition; this
new concept will have no examples; it is the null concept; it is
trivially forgettable. Merely to think of it is a blot on AM's claim
to rationality.
The "Conflict-matrix" is specified to prevent many such trivial
combinations from eating up a lot of AM's time.
If there are K features present
for the Interest facet of the concept, then its conflict-matrix will
be a K⊗7x⊗*K matrix. In row i, column j of this matrix is a letter,
indicating the relationship between features i and j:
.GROUP
.BN
E Exclusive of each other: they both can't be true at the same time.
→ Implies: If feature i holds, then feature j must hold.
← Implied by: If feature j holds, then so does feature i.
= Equal. Feature i holds precisely when feature j holds.
U Unrelated. As far as known, there is no connection between them.
.E
.APART
These little relations are utilized by some of the heuristic rules.
Here is one such rule. Its purpose is to create a new, specialized
form of concept C, if many examples of C were previously found very
quickly.
.GROUP
.B816 ONCE INDENT 4
IF Current-task is (Fillin Specializations of C)
and ||C.Examples||>30
and Time-spent-on-C-so-far < 3 cpu seconds,
and Interests(C) is not null,
.ONCE INDENT 4
THEN create a new concept named Interesting-C,
Defined as the conjunction of C.Defn and the highest-valued member of
Interests(C) which is U (unrelated) to any feature USED in the
definition of C.
and add the following task to the agenda: Fillin examples of
Interesting-C, with value computed as the Value subpart of the chosen
feature, for this reason: "Any example of Interesting-C is
automatically an interesting example of C".
and add "Interesting-C" to the USED subpart of the entry where that
feature was originally plucked from.
.E
.APART
.ONCE TURN ON "{}"
.if false then start;
Of course, the LISP form of the above rule is really more detailed
about what to do, but the general flavor of the interaction with the
Interest facet should come across. As before, the value desired is
not C.Interest, but rather the post-rippling value Interests(C).
C.Int contains a few features pertaining just to C's, but
Interests(C) contains many additional features which are not limited
in scope to merely judging C's, but pertain to a more general class
of concepts. The quantity `Time-spent-on-C-so-far' is one component
of the Worth facet of C; it might just as well have been accessed
from some "Past-history" record of AM's activities. The numbers in
the rule -- and every little bit of that rule -- were specified ad
hoc by the author. This is true for each rule initially present in
AM. As Section {[2]EXPT}.{[2]EXPTSSEC} will discuss, the precise
numbers don't drastically affect the system's performance.
.end;
. SSSEC(Suggest)
This section describes a space-saving "trick", and a "fix-up" to undo
some potentially serious side-effects of that trick.
.if false then start;
Readers not
interested in this level of detail may skip to the next subsection.
AM maintains a long list of tasks (the agenda), ordered by a global
priority rating scheme. Besides this,
.end;
AM maintains two numeric threshholds:
Do-threshhold and a lower one, Be-threshhold.
When a new task is proposed, if its global priority is below
Be-threshhold, then it won't even be entered on the agenda. This
value is set so low that any task having even one mediocre reason
will make it onto the agenda.
After a task is finished executing, the top-rated one from the agenda
is selected to work on next. If its priority rating is below
Do-threshhold, however, it is put back on the agenda, and AM
complains that no task on the agenda is very interesting at the
moment. AM then spends a minute or so looking around for new tasks,
re-evaluating the priorities of the tasks on the agenda already, etc.
One way to find new tasks (and new reasons for already-existing
tasks) is to evaluate the "⊗4Suggest⊗*" facets of all the concepts in
the system. More precisely, each Suggest facet contains some
heuristics, encoded into LISP functions. Each function accepts a
number N as an argument (representing some minimum value tolerable for a
new task), and the function returns as its value a list of new tasks.
These are then merged into the agenda, if desired.
Semantically, each function is one heuristic rule for suggesting a
new task which might be very plausible, promising, and ⊗4a propos⊗* at
the current time. For example, here is one entry from the Suggest
facet of Any-concept:
.B816 INDENT 4
IF there are no examples for concept C filled in so far,
THEN consider the task "Fillin examples of C", for the following
reason: "No examples of C filled in so far", whose value is half of
Worth(C). If that value is below arg1, then forget it; otherwise,
try to add to to the agenda.
.E
The argument "arg1" is that low numeric value, N, supplied to the
Suggest facet.
This entry alone will produce a multitude of potential tasks; for
concepts whose Worth numbers are high, or for which a task is already
on the agenda to fill in their examples, these suggested tasks will
be remembered; most of the other ones will typically be forgotten.
One use of this facet is thus to "beef up" the agenda whenever AM is
discontented with all the tasks thereon. At such a time, AM may call
on all the Suggest facets in the system, and a large volume of new
tasks will be added to the agenda. Many of them will exist there
already, but for different reasons, so many old tasks' priority
values will rise. After this period of suggesting is over, the
agenda's highest-ranking task will hopefully have a higher value than
any did before. Also at this time, the Be-threshhold and
Do-threshhold numbers are reduced. So there are two reasons why the
top task may now be rated higher than Do-threshhold. If it isn't,
then the threshholds are lowered again, and again all the Sugg facets
are triggered (this time with a lower N value).
Both threshholds are raised slightly every time AM succeeds in
picking and executing a task. So they follow a pattern of slow
increase, followed by a sudden decrement, followed by another slow
increase, etc. This was intended to mimic a human's increasing
expectations as he makes progress.
It also is suggestive of
the way a human strains his mind when an obstacle to that progress
appears; if the straining doesn't produce a brilliant new insight, he
grudgingly is willing to reduce his expectations, and perhaps resume
some "old path" abandoned earlier.
.if false then start;
Another use of this facet is to re-suggest tasks that might have been
dropped from (or never made it onto) the agenda, because they weren't
valued above Be-threshhold. How might this work? Suppose that, at an
earlier time, a task was proposed but never made it onto the agenda
because Be-threshhold was quite high. Now, suppose Be-threshhold is
much lower (due to a succession of failures). If a Sugg facet
re-proposes that same task, it will be accepted, will "stick" onto
the agenda (albeit near the bottom). The Suggest facets can
reproduce most of the common tasks, and try to stick them on the
agenda (though usually for a mediocre to poor reason). It will still
usually require another reason for such a task to rise to the very
top of the agenda, and be selected and executed.
So the use of the two threshholds is really an unaesthetic
space-saving device, and the role of the Suggest facets is merely to
correct the errors introduced in this way.
There may be no
convincing intuitive reason for having these facets at all in a
"just" world.
.end;
. SSSEC(Fillin/Check)
.QQ
To doubt everything doesn't suffice; one must know ↓_why_↓ he doubts.
-- Poincare'
.ESS
There is one more level of structure to AM's representation of a concept than
the simple "properties on a property-list" image.
Each concept consists of a bunch of facets; each
facet follows the format layed down for it (and described in the
preceding several subsections).
Yet each facet of each concept can have two additional "subfacets"
(little slots that are hung onto any desired slot) named ⊗4Fillin⊗* and
⊗4Check⊗*.
The "Fillin" field of facet F of concept C is abbreviated
C.F.Fillin. The format of that subfield is a list of
heuristic rules,
encoded into LISP functions.
Semantically, each rule in C.F.Fillin should be relevant to
filling in entries for facet F of any concept which is a C.
This substructure is an implementation answer to the question of where to place
certain heuristic rules.
As an illustration, let me describe a typical rule which is found on
Compose.Examples.Fillin.
According to the last paragraph, this must be useful for filling in
examples of any operation which is a composition.
The rule says that if the composition A-o-B is
formed from two very time-consuming operations A and B, then it's worth
trying to find some examples of A-o-B by symbolic means; in this case,
scan the examples of A and of B, for some pair of examples
x→y (example of B) and y→z (example of A). Then posit that
x→z is an example of A-o-B.
.if false then start;
This rule applies precisely to the task of filling in examples of
Examples(Composition).
Thus, it is relevant to the task "Fill in examples of Insert-o-Insert".
It is irrelevant if you change the action (e.g., "↓_⊗4Check⊗*_↓ examples of
Insert-o-Insert"), or if you change the facet to be dealt with
(e.g., "Fill in ↓_⊗4algorithms⊗*_↓ for Insert-o-Insert"),
or if you change the class of concept
(e.g., "Fill in examples of ⊗4↓_Set-union_↓⊗*)$$ Note
that it does make sense if you replace the concept "Insert o Insert"
by any other example of a Composition (e.g., "Fill in examples of
Set-Union o Set-intersection").
$.
As another illustration, let me describe a typical rule which is found on
Compose.Conjec.Fillin. It
says that one potential conjecture about a given
composition A-o-B is that it is unchanged from A (or from B). This happens
often enough that it's worth examining each time a new composition is made.
This rule applies precisely to the task of filling in conjectures about particular
compositions.
The subfacet Any-Concept.Examples.Fillin is quite large; it contains all the known
methods for filling in examples of C (when all we know is that C is a concept).
Here are a few of those techniques$$ The interested reader will find them all listed
in Appendix {[2]ALLHEU}, beginning on page {[3]ABXHP}. $:
.BN
λλ Instantiate C.Defn
λλ Search the
examples facets of all the concepts on Generalizations(C) for examples of C
λλ Run some of the concepts named in In-ran-of(C) [i.e., operations whose range
is C] and collect the resultant values.
.E
Any-Concept.Examples.Check is large for similar reasons.
A typical entry there says to examine each verified example of C: if
it is also an example of a specialization of C, then it must be removed
from C.Examples and inserted$$ Conditionally. Since each concept is of finite
worth, it is allotted a finite amount of space. A random number is generated to
decide whether or not to actually insert this example into the Examples facet of
the specialization of C. The more that specialized concept is "exceeding its quota",
the narrower the range that the random number must fall into to have that
new item inserted. The probability is never precisely 1 or 0. $
into the Examples facet of that specialized concept.
.end;
Here is one typical entry from Operation.Domain/Range.Check:
.B816 ONCE INDENT 4
IF a domain/range entry has the form (D D D... → R),
and all the D's are equal, and R is a generalization of D,
.ONCE INDENT 4
THEN it's worth seeing whether (D D D... → D)
is consistent with all known examples of the operation.
If there are no known examples,
add a task to the agenda requesting they be filled in.
If there are examples, and (D D D... → D) is consistent, add it to the Domain/range
facet of this operation.
If there are some contradicting examples, create a new concept which is defined as
this operation restricted to (D D D... → D).
.E
Note that this "Checking" rule doesn't just passively check the designated facet; it
actively "fixes up" faulty entries, adds new tasks, creates new concepts, etc.
All the check rules are very aggressive in this way.
For example, one entry on No-multiple-elements-structure.Examples.Check
will actually remove any multiple occurrences of an element from a structure.
The set Checks(C.F) of all relevant rules for
checking facet F of concept C is obtained as
(ISA's(C)).F.Check. That is, look for the Check subfacet of the
F facet of all the concepts on ISA's(C)).
Similarly, Fillins(C.F) is the union of the Fillin subfacets of the F facets of
all the concepts on ISA's(C).
When AM chooses a task like "Fillin examples of Primes", its first action is to
compute Fillins(Primes.Exs).
It does this by asking for ISA's(Primes); that is, a list of all concepts of which
Primes is an example. This list is: <Objects Any-concept Anything>.
So the relevant heuristics are gathered from Objects.Exs.Fillin, etc.
This list of heuristics is then executed, in order
(last executed are the heuristics attached to Anything.Exs.Fillin).
.if false then start;
It should now be clear what is meant when a concept's facets are
listed in the following format:
.WBOX(26,26)
MBOX Name(s) Frob, Frobnation $
MBOX ⊗8#⊗* $
MBOX ⊗8#⊗* $
MBOX Algorithms A1 A2 $
MBOX Examples E1 E2 E3 E4 E5 E6 $
MBOX Fillin Rule1 Rule2 $
MBOX Check Rule3 Rule4 Rule5 $
MBOX Domain/range DR1 DR2 DR3 $
MBOX Check Rule6 $
MBOX Conjecs C1 C2 C3 C4 C5 C6 $
MBOX Fillin Rule7 Rule8 $
MBOX Check Rule9 Rule10 $
MBOX ⊗8#⊗* $
MBOX ⊗8#⊗* $
.EBOX
.ONCE TURN ON "{}"
E.g., the entry Rule9 is a heuristic rule which may help to check
entries on the Conjecs facet of any Frob$$
`Frob' is a nonsense word, a variable identifier which stands for any concept.
$. This notation will not be
used actually in this document, partly for the benefit of those readers
who skip this subsection, partly for consistency between concepts
diagrammed before and after this subsection. Rather, all the Fillin
heuristics for a concept will be gathered together into what appears
to be just one coherent facet. Theoretically, of course, one could
organize them that way, with an extra precondition on each Fillin
heuristic to indicate which facet it is useful for filling in.
.end;
. SSSEC(Other Facets which were Considered)
Most facets (like "Definitions") were anticipated from the very beginning
planning of AM, and proved just as useful as expected. Others (like "Intuitions")
were also expected to be very important, yet were a serious disappointment.
Still others (like "Suggest") were unplanned and grumblingly acknowledged as
necessary for the particular LISP program that bears the name AM.
Finally, we turn to a few facets which were initially planned, and yet which
were adjudged useless around the time that AM was coded. They were therefore
never really a part of the LISP program AM, although they figured in its
proposal. Let me list them, and explain why each one was dropped.
.BEGIN BNN←0; INDENT 0,3,0
λλ UN-INTERESTINGNESS. This was to be similar to the Interest part. It would
contain entries of the form feature/value/reason, where the feature would be
a ⊗4bad⊗* (dull, trivializing, undesirable, uninteresting) property that an
entity (a concept or a task) might possess.
If it did, then the value component would return a
negative number as its contribution to the worth/priority of that entity.
This sounded plausible, but turned out to be useless in practice:
(i) There were very few features one could point to which explicitly indicated
when something was boring; (ii) Often, a conjunction of many such features
would make the entity seem unusual, hence interesting; (iii) Most entities
were viewed as very mediocre unless/until specific reasons to the contrary,
and in those cases the presence a few boring properties would be outshadowed
by the few non-boring ones. In a sea of mediocrity, there is little need to
separate the boring from the very boring.
λλ JUSTIFICATION.
For conjectures
which were not yet believed with certainty, this part would contain all the known
evidence supporting hem.
This would hopefully be convincing, if
the user (or a concept) ever wanted to
know.
In cases of contradictions arising
somehow, this facet was to keep hold of the threads that could be untangled
to resolve those paradoxes. As described earlier, this duty could naturally be
assumed by the Conjecs facet of each concept. The other intended role for this
facet was to hold sketches of the proofs of theorems.
Unfortunately, the intended concepts for Proof and Absolute truth were
never implemented, and thus most of the heuristic rules which would have interacted
with this facet are absent from AM. It simply was never needed.
λλ RECOGNITION
Originally, it was assumed that the location of relevant concepts and
their heuristics would be much more like a
free-for-all (pandemonium) than an orderly rippling process.
As with the original use of BEINGs$$ Interacting knowledge modules, each module
simulating a different expert at a round-table meeting. See [Lenat 75b]. $, the
expectation was that each concept would have to "shout out" its relevance whenever
the activities triggered some recognition predicate inside that concept.
Such predicates were to be stored in this facet.
But it quickly became apparent that the triggering predicates which were the
left-hand-sides of the heuristic rules were quick enough to obviate the need
for pre-processing them too heavily. Also, the only rules relevant to a given
activity on concept C always seemed to be attainable by rippling in a certain
direction away from C. This varied with the activity, and a relatively small table
could be written, to specify which direction to ripple in (for any given desired
activity). We see that for "Fill-in examples of...", the direction to ripple in
is "Generalizations", to locate relevant heuristic rules.
For "Judge interest of..." the direction is also generalizations. For
"Access specializations of", the direction is Specializations, etc.
The only important point here is that the Recognition facet was no longer needed.
.E
.SSEC(AM's Starting Concepts)
.CDIAG: PAGE;
.ONCE TURN ON "{}"
The first subsection presents a diagram of the top-level (general)
concepts AM started with, with the lines indicating the
Generalizations/Specializations kinds of relationships (single line
links) and a few Examples/Isa's links (triple vertical lines).
Several specific concepts have been omitted from that picture. All
the concepts initially fed to AM are then listed alphabetically and
described in Section {SECNUM}.{SSECNUM}.2.
.if false then start;
A full facet-by-facet
description of each concept is provided in Appendix {[2] ALLCON}.
.end;
Finally, Section {SECNUM}.{SSECNUM}.3 discusses
the choice of starting concepts.
. SSSEC(Diagram of Initial Concepts)
.B0
.TREECON: PAGE;
Anything
/ \
/ \
/ \
Any-concept ⊗4non-concepts⊗*
/ \
/ \
/ \
/ \
⊂∂∂∂∂∂∂∂∂∂Activity Object
} / \ / } \
Relation / \ / } \
/ Predicate Operation Atom Conjec Structure∂∂∂∂∂∂∂∂⊃
Logical-reln / \ } } / } } }\ }
Constant-pred Equality-pred } Truth-value / } } } \ Struc-of-strucs
.ONCE TURN OFF "⊗"
⊗ ⊗ ⊗ } / } Empty} \
.ONCE TURN OFF "⊗"
⊗ ⊗ ⊗ ∪ / } } \
Const-T Const-F Obj-equal ∩ Mult-eles Non-mult Ord Unordered
∪ \ \ \ \ / } / /
Coalescing \ \ \ Osets }/ /
Inverted-operation \ \ \ / /
Canonization \ \ \ /} /
Composition \ \ Sets } /
Restricted-operation \ \ } /
# \ \ ∪ /
# \ \ ∩ /
\ \ ∪ /
\ Lists /
\ \ /
\ \ /
\ ∃
\ / \
Bags \
Ord-pairs
.E
The diagram above represents the "topmost" concepts
which AM had initially,
shown connected via
Specialization links (⊗8\⊗*) and Examples links (⊗8α⊗⊗*).
The only concepts not diagrammed are ⊗4examples⊗* of the concept Operation.
There are 47 such operations.
Also, we should note that many entities exist in the system
which are not themselves concepts. For example, the number "3", though it
be an ⊗4example⊗* of many concepts, is not itself a concept.
All entities which ⊗4are⊗* concepts are present on the list called
CONCEPTS, and they all have property lists (with facet names as the
properties). In hindsight, this somewhat arbitrary scheme is regrettable.
A more aesthetic designer might have come up with a more uniform system
of representation than AM's.
. SSSEC(Summary of Initial Concepts)
.ONCE TURN ON "{}"
Since the precise set of concepts is not central to the design of AM,
or the quality of behaviors of AM, they are not worth detailing here.
On the other hand, a cursory familiarity with their names and
definitions should aid the reader in building up an understanding of
what AM has done. For that reason, the concepts will now be briefly
described, in alphabetical order. This is the same order as concepts
are listed on page {[3]ENDINDEXCP}.
.if false then start;
A fuller description of the
concepts is provided in Appendix {[2] ALLCON}. The ordering within
that appendix is different; concepts are grouped together if they are
semantically related, by starting at the top of the diagram and
meandering downward.
.end;
.BRIEFC: PAGE;
⊗6ACTIVITY⊗* represents something that can be "performed". All
Actives -- and ⊗4only⊗* Actives -- have Domain/range facets and
Algorithms facets.
⊗6ALL-BUT-FIRST-ELEMENT⊗* is an operation which takes an ordered
structure and removes the first element from it. It is similar in
spirit to the Lisp function "CDR".
⊗6ALL-BUT-LAST-ELEMENT⊗* takes an ordered structure and removes its
last element.
⊗6ANY-CONCEPT⊗* is useful because it holds all the very general
tactics for filling in and checking each facet. The definition of
Any-concept is ⊗6"λ (x) xεCONCEPTS"⊗*. `⊗6CONCEPTS⊗*' is AM's global
list of entities known to be concepts. Initially, this list contains
the hundred or so concepts which AM starts with (e.g., all those
diagrammed on the preceding page).
⊗6ANYTHING⊗* is defined as ⊗6"λ (x) T"⊗*; i.e., a predicate which
will ⊗4always⊗* return true. Notice that the singleton {a} is an
example of Anything, but (since it's not on the list ⊗6CONCEPTS⊗*) it
is not an example of Any-concept.
⊗6ATOM⊗* contains data about all primitive, indivisible objects
(identifiers, constants, variables).
⊗6BAG⊗* is a type of structure. It is unordered, and multiple
occurrences of the same element are permitted. They are isomorphic to
the concept known as `multiset', except that we stipulate that sets
are ⊗4not⊗* bags.
⊗6BAG-DELETE⊗* is an operation which takes two arguments, x and B.
Although x can be anything, B must be a bag. The procedure is to
remove one occurrence of x from B.
⊗6BAG-DIFF⊗* is an operation which takes two bags B,C. It repeatedly
picks a member of C, and removes it (one occurrence of it) from both
B and C. This continues until C is empty.
⊗6BAG-INSERT⊗* is an operation which adds (another occurrence of) x
into bag B.
⊗6BAG-INTERSECT⊗* takes two bags B,C, and creates a new bag D. An
item occurs in D the ⊗4minimum⊗* number of times it occurs in either
B or C.
⊗6BAG-UNION⊗* takes bag C and dumps all its elements into bag B.
⊗6CANONIZE⊗* is both an example of and a specialization of
`Operation'. It accepts two predicates P1 and P2 as arguments, both
defined over some domain A⊗7x⊗*A, where P1 is a generalization of P2.
Canonize then tries to produce a "standard representation" for
elements of A, in the following way. It creates an operation f from A
into A, satisfying: ⊗6P1(x,y) iff P2(f(x),f(y))⊗*. Then any item of
the form f(x) is called a canonical member of A. The set of such
canonical-A's is worth naming, and it is worth investigating the
restrictions of various operations' domains and ranges to this set of
canonical-A's$$ i.e., take an operation which used to have "A" as one
of its domain components or as its range, and try to create a new
operation with essentially the same definition but whose domain/range
says "Canonical-A" instead of "A". $. "Canonize" contains lots of
information relevant to creating such functions f (given P1 and P2).
Thus Canonize is an example of the concept Operation. Canonize also
contains information relevant to dealing with any and all such f's.
So Canonize is a specialization of Operation.
⊗6COALESCE⊗* admits the same duality$$ Both a specialization of
Operation and an example of Operation. $. This very useful operation
takes as its argument any operation F(a,b,c,d...), locates two domain
components which intersect (preferably, which are equal; say the
second and third), and then creates a new operation G defined as
G(a,b,d...)⊗6≡⊗*F(a,b,b,d...). That is, F is called upon with a pair
of arguments equal to each other. If F were Times, then G would be
Squaring. If F were Set-insert, then G would be the operation of
inserting a set S into itself.
⊗6COMPOSITION⊗* involves taking two operations A and B, and applying
them in sequence: A-o-B(x)⊗6≡⊗*A(B(x)). This concept deals with (i)
the activity of creating new compositions, given a pair of
operations; (ii) all the operations which were created in this
fashion. That is why this concept is both a specialization of and an
example of Operation.
⊗6CONJECTURES⊗* are a kind of object. This concept knows about -- and
can store -- conjectures. When proof techniques are inserted into AM,
this tiny twig of the tree of concepts will grow to giant
proportions.
⊗6CONSTANT-PREDICATE⊗* is a predicate which can afford to have a very
liberal domain: it always ignores its arguments and just returns the
same logical value all the time.
⊗6DELETE⊗* is an operation which contains all the information common
to all flavors of removing an element from a structure (regardless of
the type of structure which is being attenuated). When called upon
to actually perform a deletion, this concept determines the type of
structure and then calls the appropriate specialized delete concept
(e.g., Bag-delete).
⊗6DIFFERENCE⊗* is another general operation, which accepts two
structures, determines their type (e.g., Bags), and then calls the
appropriate specialized version of difference (e.g., Bag-diff).
⊗6EMPTY-STRUCTURE⊗* contains data relevant to structures with no
members.
⊗6FIRST-ELEMENT⊗* is an operation which takes an ordered structure
and returns the first element. It is like the Lisp function `CAR'.
⊗6IDENTITY⊗* is just what it claims to be. It takes one argument and
returns it immediately. The main purpose of knowing about this boring
transformation is just in case some new concept turns out
unexpectedly to be equivalent to it.
⊗6INSERT⊗* takes an item x and a structure S, determines S's type,
and calls the appropriate flavor of specialized Insertion concept.
The general INSERT concept contains any information common to all of
those insertion concepts.
⊗6INTERSECT⊗* is an operation which computes the intersection of any
two structures. It, too, has a separate specialization for Bags,
Sets, Osets, and Lists.
.ONCE TURN OFF "-"
⊗6INVERT-AN-OPERATION⊗* is a very active concept. It can invert any
given operation. If F:X→Y is an operation, then its inverse will be
abbreviated F-1-, and F-1-(y) is defined as all the x's in X for
which F(x)=y. The domain and range of F-1- are thus the range and
domain of F.
⊗6INVERTED-OP⊗* contains information specific to operations which
were created as the inverses of more primitive ones.
⊗6LAST-ELEMENT⊗* takes an ordered structure and returns its final
member.
⊗6LIST⊗* is a type of structure. It is ordered, and multiple
occurrences of the same element are permitted. Lists are also called
vectors, tuples, and obags (for "ordered bags").
⊗6LIST-DELETE⊗* is an operation which takes two arguments, x and B.
Although x can be anything, B must be a list. The procedure is to
remove the first occurrence of x from B.
⊗6LIST-DIFF⊗* is an operation which takes two lists B,C. It
repeatedly picks a member of C, and removes it (the first remaining
occurrence of it) from both B and C. This continues until there are
no more members in C.
.SELECT 1
⊗6LIST-INSERT⊗* is an operation which adds (another occurrence of) x
onto the front of list B. It is like the Lisp function `CONS'.
⊗6LIST-INTERSECT⊗* takes two lists B,C, and creates a new list D. An
item occurs in D the ⊗4minimum⊗* number of times it occurs in either
B or C. D is arranged in order as (a sublist of) list B.
⊗6LIST-UNION⊗* takes list C glues it onto the end of list B. It's
like `APPEND' in Lisp.
⊗6LOGICAL-RELATION⊗* contains knowledge about Boolean combinations:
disjunction, conjunction, implication, etc.
⊗6MULTIPLE-ELEMENTS-STRUCTURES⊗* are a specialization of Structure.
They permit the same atom to occur more than once as a member. (e.g.,
Bags and Lists)
⊗6NO-MULTIPLE-ELEMENTS-STRUCTURES⊗* are a specialization of
Structure. They permit the same atom to occur only once as a member.
(e.g., Sets and Osets)
⊗6NONEMPTY-STRUCTURES⊗* are a specialization of Structure also. They
contain data about all structures which have some members.
⊗6OBJECT⊗* is a general, static concept. Objects are like the
subjects and direct objects in sentences, while the Actives are like
the verbs$$ As in English, a particular Activity can sometimes itself
be the subject. $.
⊗6OBJECT-EQUALITY⊗* is a predicate. It takes a pair of objects, and
returns True if (i) they are identical, or (ii) they are structures,
and each corresponding pair of members satisfies Object-Equality.
Often we'll call this `Equal', and denote it as `='.
⊗6OPERATIONS⊗* are Actives which take arguments and return a value.
While a predicate examines its arguments and returns either True or
False, an operation examines ⊗4its⊗* arguments and returns any number
of values, of varying types. Assuming that the arguments lay in the
domain of the operation (as specified by some entry on its
Domain/range facet), then every value returned must lie within its
range (as specified by that same Domain/range entry).
⊗6ORDERED-PAIR⊗* is a kind of List. It has just two `slots', however:
a front and a rear element.
⊗6ORDERED-STRUCTURE⊗* is a specialized type of Structure. It includes
all structures for which the order of insertion of two members can
make a difference in whether the structures are equal or not.
Ordered-structures are those for which it makes sense to talk about a
front and a rear, a first element and a last element.
⊗6OSET⊗* is a type of structure. It is ordered, and multiple
occurrences of the same element are not permitted. The
short-term-memory of Newell's PSG [Newell 73] is an Oset, as is a cafeteria
line. Not much use was found for this concept by AM.
⊗6OSET-DELETE⊗* removes x from oset B (if x was in B).
⊗6OSET-DIFF⊗* is an operation which takes two osets B,C. It removes
each member of C from B.
⊗6OSET-INSERT⊗* is an operation which adds x to the front of oset B.
If x was in B previously, it is simply moved to the front of B.
⊗6OSET-INTERSECT⊗* takes two osets B,C, and removes from B any items
which are ⊗4not⊗* in C as well. B thus `induces' the ordering on the
resultant oset.
⊗6OSET-UNION⊗* takes oset C, removes any elements in B already, then
glues what's left of C onto the rear of B.
⊗6PARALLEL-JOIN⊗* is an operation which takes a kind of structure and
an operation H. It creates a new operation F, whose domain is that
type of structure. For any such structure S, F(S) is computed by
appending together H(x) for each member x of S.
⊗6PARALLEL-JOIN2⊗* is a similar operation. It creates an operation F
with two structural arguments. F(S,L) is computed by appending the
values of H(x,L), as x runs through the elements of S.$$Here, the
args to PARALLEL-JOIN2 are two types of structures SS and LL, and an
operation H whose range is also a structural type DD. Then a new
operation is created, with domain SSxLL and range DD. $
⊗6PARALLEL-REPLACE⊗* is an operation used to synthesize new
substitution operations. It takes a structural type and an operation
H as its arguments, and creates a new operation F. F(S) is computed
by simply replacing each member x of S by the value of F(x). The
operation produced is very much like the Lisp function MAPCAR.
⊗6PARALLEL-REPLACE2⊗* is a slightly more general operation. It
creates F, where F(S,L) is computed by replacing each x⊗6ε⊗*S by
F(x,L).
⊗6PREDICATES⊗* are actives which examine their arguments and then
return T or NIL (True or False). It is only due to the
capriciousness of AM's initial design that predicates are kept
distinct from operations. Of course, each example of an operation
can be viewed as if it were a predicate; if F:A→B is any operation
from A to B, then we can consider F a relation on AxB, that is a
subset of AxB, and from there pass to viewing F as a (characteristic)
predicate F:AxB→α{T,Fα}. Similarly, any predicate on Ax...xBxC may
be considered an operation (a multi-valued, not-always-defined
function) from Ax...xB into C. There are no unary predicates. If
there were one, say P:A→{T,F}, then that predicate would essentially
be a new way to view a certain subset of A; the predicate would then
be transformed into {a⊗6ε⊗*A|P(a)}, made into a new concept, tagged
as a specialization of A, and its definition would be "λ(a)
[A.Defn(a) ∧ P(a)]".
⊗6PROJECTION1⊗* is a simple operation. It is defined as ⊗6λ (x y)
x⊗*. Notice that Identity is just a specialized restriction of
Proj1. Proj1(Me,You)=Me.
⊗6PROJECTION2⊗* is a similar operation. It is defined as ⊗6λ (x y)
y⊗*.
⊗6RELATION⊗* is any Active which has been encapsulated into a set of
ordered pairs. `Relation' bridges the gap between active and static
concepts.
⊗6REPEAT⊗* is an operation for generating new operations by repeating
old ones. Given as its argument a structural type SS and an existing
operation H (with domain and range of the form SSxSS→SS),
Repeat(SS,H) synthesizes a brand new operation F. The domain/range of
F is just that of H. F(S) is computed by repeating TEMP←H(x,TEMP) for
each element x of S. TEMP is initialized as some member (preferably
the first element) of S.
⊗6REPEAT2⊗* is similar, but requires that H take three arguments, and
it creates F, where F(S,L) is gotten by repeatedly doing
TEMP←H(x,TEMP,L).
⊗6RESTRICT⊗* is an operation which turns out new
operations. Given an argument operation (or predicate) F, the synthesized
concept
would have the same definition as F, but would have its domain and/or
range curtailed.
⊗6REVERSE-ORDERED-PAIR⊗* transforms the ordered pair <x,y> into
<y,x>.
⊗6SET⊗* is a type of structure. It is unordered, and multiple
occurrences of the same element are not permitted.
⊗6SET-DELETE⊗* is an operation which takes two arguments, x and B.
Although x can be anything, B must be a set. The procedure is to
remove x from B (if x was in B), then return the resultant value of
B.
⊗6SET-DIFF⊗* is an operation which takes two sets B,C. It removes
each member of C from B.
⊗6SET-INSERT⊗* is an operation which adds x to set B.
⊗6SET-INTERSECT⊗* removes from set B any items which are ⊗4not⊗* in
set C, too.
⊗6SET-UNION⊗* dumps into B all the members of C which weren't in
there already.
⊗6STRUCTURE⊗*, the antithesis of ATOM, is inherently divisible. A
structure is something that has members, that can be broken into
pieces. There are two questions one can ask about any kind of
structure: Is it ordered or not? Can there be multiple occurrences of
the same element in it or not? There are four sets of answers to
these two questions, and each of the four specifies a well-known kind
of structure (Sets, Lists, Osets, Bags).
⊗6STRUCTURE-OF-STRUCTURES⊗* is a specialization of Structure, representing
those structures all of whose ⊗4members⊗* are themselves structures.
⊗6TRUTH-VALUE⊗* is a specialized kind of atomic object. Its only
examples are True and False. This concept is the range set for all
predicates.
⊗6UNION⊗* is a general kind of joining operation. It takes two
structures and combines them. Four separate variants of this concept
are given to AM initially (e.g., Set-union).
⊗6UNORDERED-STRUCTURE⊗* is a specialized type of Structure. It
includes all structures for which the order of insertion of two
members never makes any difference in whether the structures are
equal or not. Unordered-structures cannot be said to have a front or a
rear, a first element or a last element.
. SSSEC(Rationale behind Choice of Concepts)
A necessary part of realizing AM was to choose a
particular set of starting concepts. But how should such a choice be
made?
My first impulse was to gather a ⊗4complete⊗* set of concepts. That
is, a basis which would be sufficient to derive all mathematics. The
longer I studied this, the larger the estimated size of this basis
grew. It immediately became clear that
this would never fit in 256k. $$ This is the size of the core memory
of the computer I had at my disposal. $ One philosophical problem
here is that future mathematics may be inspired by some real-world
phenomena which haven't even been observed yet. Aliens visiting Earth
might have a different mathematics from ours, since their collective
life experiences could be quite different from we Terrans.
Scrapping the idea of a sufficient basis, what about a necessary one?
That is, a basis which would be ⊗4minimal⊗* in the following sense:
if you ever removed a concept from that basis, it could never be
re-discovered. In isolated cases, one can tell when a basis is
⊗4not⊗* minimal: if it contains both addition and multiplication,
then it is too rich, since the latter can be derived from the
former.$$ by AM, and by any mathematician. As Don Cohen points out,
if the researcher lacked the proper discovery methods, then he might
never derive Times from Plus. $ And yet, the same problem about
"absoluteness" cropped up: how can anyone claim that the discovery of
X can ⊗4never⊗* be made from a given starting point? Until recently,
mathematicians didn't realize how natural it was to derive numbers
and arithmetic from set theory (a task which AM does, by the way)$$
The "new math" is trying to get young children to do this as well;
unfortunately, no one showed the elementary-school teachers the
underlying harmony, and the results have been saddening. $. So 50
years ago the concepts of set theory and number theory would both
have been undisputedly placed into a "minimal" basis. There are thus
no absolute conceptual primitives; each culture (perhaps even each
individual) possesses its own basis.
Since I couldn't give AM a minimal basis, nor a complete one, I
decided AM might as well have a ⊗4nice⊗* one. Although it can never
be minimal, it should nevertheless be made very small (order of
magnitude: 100 concepts). Although it can never be complete, it
should suffice for re-discovering much of already-known mathematics.
Finally, it should be ⊗4rational⊗*, by which I mean that there should
be a simple rule for deciding which concepts do and don't belong in
that basis.
The concepts AM starts with are meant to be those possessed by young
children (age 4, say). This explains some omissions of concepts which
would otherwise be considered fundamental: (i) Proof and techniques
for proof/disproof; (ii) Abstract properties of relations, like
associativity, single-valued, onto; (iii) Cardinality, arithmetic;
(iv) Infinity, continuity, limits. The interested reader should see
[Piaget 55] or [Copeland 70].
Because my programming time and the PDP-10's memory space were both
quite small, only a small percentage of these `pre-numerical'
concepts could be included. Some unjustified omissions are: (i)
visual operations, like rotation, coloration; (ii) Games, rules,
procedures, strategies, tactics; (iii) Geometric notions, e.g.,
outside and between.
AM is not supposed to be a model of a child, however. It was never
my intention (and it would be much too hard for me) to try to emulate
a human child's whimsical imagination and emotive drives. And AM is
not ripe for "teaching", as are children.$$ Learning psychologists
might label AM as neo-behavioristic and cognitivistic. See
[LeFrancois]. $
Also, though it possesses a child's ignorance of most concepts, AM is given
a large body of sophisticated "adult" heuristics. So perhaps
a more faithful image is that of Ramanujan, a
brilliant modern mathematician who received a very poor education,
and was forced to re-derive much of known number theory all by
himself. Incidentally, Ramanujan never did master the concept of formal proof.
.ONCE TURN ON "{}"
There is no formal justification for the particular set of starting
concepts. They are all reasonably primitive (sets, composition), and
lie several levels "below" the ones which AM managed to ultimately
derive (prime factorization, square-root). It might be valuable to
attempt a similar automated math discoverer, which began with a very
different set of concepts (e.g., start it out as an expert in lattice
theory, possessing all known concepts thereof). The converse kind of
experiments are to vary the initial base of concepts, and observe the
effects on AM's behavior. A few experiments of that form are
described in Section {[2]EXPT}.{[2]EXPTSSEC}.